Ok, I have the same problem with my recent documents icon not changing. Here's the thing, though. I've found the "recent" folder like you describe above and changed the icon for it manually - but the default windows folder icon still sits there unchanged in the start menu!
Is there anything else I can try?