Are you using the clone tool or are you using the brush tool? They work entirely differently. Using the brush tool to cover up an area won't work like the clone tool. I'm going to assume when you mentioned 'brush' you were referring to the brush choice when using the clone tool not that you used the regular brush tool for this purpose.
To start with -- you aren't removing anything with the clone tool, you are covering up by putting something new over the area. By saying something is left over when you use the clone leads me to think you are not using the clone tool. However, it could just be that the brush you are using with the clone tool is a soft one and you are seeing feathering around your cloning. Wherever there is a feathered area of your clone, there will be less opacity and your original area will show through that feathered area.
When using the clone tool, you choose what part of your photo you will use to stamp over the area you are fixing. You hold down the alt/option key and click on an area and you grab a part of that area - the area you 'grabbed' is then stamped over the area you wish to cover up. You move over to the area and click - this stamps whatever you choose with the alt/option key OVER the area you wish to cover up. Careful cloning choice should prevent shadowing. Making frequent new choices while cloning should help, too. Changing the choice size while cloning will help you finesse it.
Your problem is probably brush choice. Choosing a different brush to clone with may help. A brush with a soft edge will leave an area of softness around your cloning. This is a good thing when you are cloning things like leaves, etc., but not good if you want to clone a hard edge. Changing to a hard edged brush to clone a hard edge, should help.
There are also different modes for the clone tool - I usually use normal, so I'm not familiar with how the other modes act. However, your problem may be that you are using one of the other modes.
If after all this - you still think the clone tool is acting funny, try resetting the tool. If the tool options are at the bottom of your screen in your version of PSE, you will find reset at the far right of your tool options bar. It looks like a few lines - click on that and 'reset' is an option. If your option bar is at the top of your screen, you'll have to look around for reset, I don't remember where it is on older versions of PSE. Once you reset it, it will go back to the most used options - so that might be a good place to learn how to use the clone tool because the settings will be at their best choice.
