Problem With Cropping

[db_shotgun_girl]

I've been noticing when cropping an picture to icon size, that it's been putting this weird looking gray edge sort of thing around all four sides of the icon. Sometimes, I can fix the problem by using a light blur or smudge brush, but sometimes it's (as in the gray lines) too strong to do that. Is there something I can do to stop this from happening, because imo it's making my icons look pretty tacky =(

Totally forgot to say I'm using Photoshop CS3 and that I'm using a single screencap, I always crop before adding coloring etc. Should I wait until the end to crop?

* edit * The advice given works wonders, thanks a lot :)