The problem is you're cloning from such a small area that your pattern is becoming too repetitive so it looks unnatural. And yeah, because you cloned out her shadow entirely, she looks like she's no longer grounded - she looks entirely cut out and pasted rather than like she actually belongs.
The first thing I would recommend doing is duplicate your background layer in photoshop. Open up your layers palette (window -> layers) and click "background layer," drag it down to the New Layer icon (second to the right). Now you should have Background Layer and Background Copy.
Then click the little eye next to the layer that says "background layer."
Make sure you've selected your background copy layer, and using a fairly soft brush and the eraser tool, I'd erase out from around her. Once you have her clean you should be able to work on the background behind her without screwing up the actual outline of the dog.
I would probably duplicate the background layer again instead of working directly on it for your actual background, too, just so you never mess up your original layer.
Then use a large, soft brush with your clone tool. Every now and then move where you are cloning from and cross back and forth a little to make sure your edges are blending and you aren't creating a really repetitive background.
Here's my go at it.