Custom icons won't change

A couple years ago I made custom icons for some folders (made the images in Photoshop, set ti 1024x1024 pixels, copied and pasted into the icon in get info). Now I want to change them. If I just delete the existing icon, the default folder icon reappears. However, even if I then restart the computer, when I try to put a new custom icon onto the folder, the old one reoccurs. Sometimes it works, and I haven't been able to come up with a reason why. This has been demonstrated on my MacBook Pro (MacOS 10.4.6) and my old MacPro (10.4.5). On the MacPro, one of the folders suddenly changed to the new icon, nearly an hour after I had pasted the new one in get info; one worked immediately; and the rest keep reverting to the previous icons. On the MacBook Pro, one icon worked immediately but none of the others -- and, interestingly, the one icon that worked immediately was the same for both computers. Hierarchically, two of the folders are inside one of the others, if that makes a difference.

Any suggestions on how to make the new icons stick instead of the old ones? I've tried moving folders to new locations, making aliases and pasting the icon on the alias, and every other idea I found regarding adding new custom icons to folders.

Thanks!