Try using
Pixadex. IIRC, I had the same problem while back, trying to put an icns icon onto my iPod. I think you load your icon into Pixadex, put it into the QuickDrop zone, then drag the folder whose icon you want to change onto there. For some reason, this works while copy/paste through Finder doesn't work - that sounds like what you've been trying.