Use Mail::RFC822::Address. Also, the Regular Expression Library has some pretty interesting constructs.
As to your regex, I don't see anything wrong in it, and it works with a couple of test cases as it should:
$ perl -e 'print "valid\n" if ("foo\@bar" =~ m/^[a-zA-Z_\-.0-9]+@[a-zA
$ perl -e 'print "valid\n" if ("j.random.hacker\@perlmonks.com" =~ m/^
Of course, tests can never show the absence of errors. But I'm willing to bet you have a problem somewhere else in the program.
UPDATE: Seems like others beat me to it... I just remembered that there was some nice discussion about this over at The Daily WTF.