I think the alias has had it's icon changed successfully, it just isn't been shown by Finder yet.
Okay, go through with the method you know, create a new folder alias then change it's icon.
Copy the alias with it's altered icon, onto the Desktop, hopefully this should be enough to force Finder to show the new icon (If successful, jump up in the air & scream Hip Hip Hoorah, then just delete the other alias).
If it doesn't, restart Finder by going to the in the upper left menubar & choose "Force Quit".
You'll be warned about saving changes etc so make sure you cover those bases.
When Finder restarts, hopefully the folder alias' new icon should be showing.