How to set "date added" metadata in Mac OS X 10.7 Lion
When I run xattr -l on items in my Downloads folder, I get a field that looks something like this:

com.apple.metadata:kMDItemDownloadedDate:
00000000  62 70 6C 69 73 74 30 30 A1 01 33 41 B4 83 4D BF  |bplist00..3A..M.|
00000010  4C 4F E3 08 0A 00 00 00 00 00 00 01 01 00 00 00  |LO..............|
00000020  00 00 00 00 02 00 00 00 00 00 00 00 00 00 00 00  |................|
00000030  00 00 00 00 13                                   |.....|
00000035


This is a binary plist. When I use HexFiend to create a file with those bytes (yes, I manually entered them; blast from the past like entering assembler code out of a magazine into my Apple ][GS), then save it as a .plist file, I opened the file in TextWrangler and got the following uncompiled xml:

&lt;?xml version="1.0" encoding="UTF-8"?&gt;
&lt;!DOCTYPE plist PUBLIC "-//Apple//DTD PLIST 1.0//EN" "http://www.apple.com/DTDs/PropertyList-1.0.dtd"&gt;
&lt;plist version="1.0"&gt;
&lt;array&gt;
    &lt;date&gt;2011-11-28T05:03:59Z&lt;/date&gt;
&lt;/array&gt;
&lt;/plist&gt;


That said, while Apple seems to store the dates in compiled XML, plain text seems to work.

In other words, if you can get the file's modified date in string form, you can run the command xattr -w com.apple.metadata:kMDItemDownloadedDate "2012-02-19 16:34:47 +0000" file to change the "downloaded date", which appears to be the field actually sorted on, not actual Date Added.

Finally you got no error when adding the (unused) kMDItemDateAdded field because, as I learned in this article, xattr will happily set whatever metadata field you want, used or unused.

That's the core of the answer. I'll work on writing an AppleScript to get the modified date for each file, check to see if kMDItemDownloadedDate is set, and if it isn't, set kMDItemDownloadedDate to the modified date, but I wanted to get the core of the answer posted.