FWIW, your CGI-script works fine here: perl v5.10.0, openSuSE 11.1, Time::Format 1.09. Works both - with root and non-privileged users.

However, It seams that Time::Format is checking if an XS version is available. Maybe it is crashes while doing so or while doing the parsing later on?

# Here we go through a bunch of tests to decide whether we can use the
# XS module, or if we need to load and compile the perl-only
# subroutines (which are stored in __DATA__).
my $load_perlonly = 0;
$load_perlonly = 1  if defined $Time::Format::NOXS  &&  $Time::Format:
+:NOXS;
[download]

Maybe adding

...
BEGIN { $Time::Format::NOXS=1; }
use Time::Format;
...
[download]

to your CGI helps?

Update: forgot to add: while doing the parsing later on
Update2: clarified, that Time::Format::NOXS had to be set prior to using the module.
Update3: Now, since this experiment was successful, it seems that the problem is correlated with the usage of the XS based module (or something depending on that).
Things you could try:

• as AM said: check under your webservers UID, then
• check/compare environment variables, esp. LANG, LD_LIBRARY_PATH, PERL*
• strace perl script.cgi (under both UIDs)
• re-compile/re-install the XS module
• ...