It sounds identical to your problems, but this time with Amazon's S3:
http://developer.ama...=34076&tstart=150
[edit:] Yet more gotchas that may or may not apply: http://www.dns.net/d...tml#cname-targets
Dunno if any of this is helpful. I found these links by searching on "dns cname not propagating" (without the quotes).
Good luck!
Cheers,
Scott.