This was reported - believe or not back in 2009 as a bug-report.
I've test this on lucid, natty and oneiric and confirm the fixed bug-report was incorporated into oneiric. It hasn't been backported to earlier versions of Ubuntu.
There is a proposed code patch.
Thus - if you definitely want this in Lucid, you will need to compile a custom version of nautilus :(
I can confirm that the patch in question does work in lucid...
If you are interested in trying this custom version of nautilus I've created a PPA with the patch applied to the source code.
sudo add-apt-repository ppa:fossfreedom/nautilus
sudo apt-get update
sudo apt-get install nautilus
Logout and login
Use the linked question to assign a custom icon to the folder. When you create a bookmark for an item within the folder, the bookmark folder icon will inherit the icon of the associated folder containing the file.
How can I assign custom icons to folders?