Maybe it's a cannon to kill a fly (or has some problems I don't know about), but I've always used the pure-perl Date::Format module without any problems. The following should print out the recommended yyyy-mm-dd format:

use Date::Format;
print time2str( '%Y-%m-%e', time );
[download]

or from the command-line:

perl -MDate::Format -e 'print time2str( "%Y-%m-%e", time )'
[download]

Chris
M-x auto-bs-mode