Eh? That's not true at all... versions of Mac OS X prior to Leopard defaulted to downloading things to the desktop. Leopard and later have a dedicated Downloads folder in each user's home folder for this purpose.Are you sure the Downloads folder was in your User folder? The default location is the Root.
You should have write permissions for your home folder, so just create a folder and name it Downloads. Mac OS X takes care of the icon-related magic for you.
If you can't create a folder in your home directory, it sounds like you have permissions problems.
Open Disk Utility and run a permissions repair on your system hard drive, then reboot.
If you do a "Get Info" on your home folder, what does it say about the permissions?