"Bad response to Storage command" when scheduling job with Bacula

I have a Bacula setup with 9 clients, and it's working happily. Today I had to add another client, so I went and copied+adapted the existing configuration files from another client, but when I schedule a job for the new client, I get these errors:

20-Mar 17:50 tools-dir JobId 39: Start Backup JobId 39, Job=BackupPresenze2.2012-03-20_17.50.49_04
20-Mar 17:50 tools-dir JobId 39: Using Device "FileStorage"
20-Mar 17:50 presenze2-fd JobId 39: Fatal error: Failed to connect to Storage daemon: bacula.mylan.local:9103
20-Mar 17:50 tools-dir JobId 39: Fatal error: Bad response to Storage command: wanted 2000 OK storage
, got 2902 Bad storage

From the client I can telnet to bacula.mylan.local:9103 just fine, and jobs for other clients work successfully... What could I check?
(Server and client run Ubuntu 10.04, if it's relevant)

It looks like it was a "slow DNS" kind of problem... I added the hostname to /etc/hosts and now Bacula works happily.

In my case it was firewall - FD (client) could not connect to SD (storage daemon) to port tcp/9103. But director could normally retrieve client status with status client=myclient-fd (as DIR could connect to FD to port tcp/9102)

The error is confusing as on causal look it sounds like SD is returning error to FD (which would imply that FD could connect to SD afterall), while in reality it is DIR noticing that FD did not connect to SD and issuing error.