I was messing with this myself a little while ago, and had similar problems. It appears that in order for Sys::Syslog to function properly, the syslog daemon must actually be running with the -r flag set. From the syslogd manpage:

 -r  This  option  will  enable  the facility to receive
     message from the network using an  internet  domain
     socket  with  the syslog service (see services(5)).
     The default is to not receive any messages from the
     network.
[download]

So, even if your Perl script is running on the same machine as the syslog daemon, you still need to use the -r flag.

Beware, however, that running syslog with -r opens the door for security issues. Now, anyone can send messages to your syslog daemon. You may wish to use some sort of firewall rules to block incoming traffic to your syslog daemon from the outside world.

Good luck!
-Eric