Ok, I was right, DBUS was somehow related.
The problem was more complex and the agent was just a "victim" of something bigger.
Basically, DBUS was not starting properly. In fact, the polkit-agent was not the only service unable to start: network manager, gnome-power-manager, bluetooth stuff, etc. were amongst the missing pieces.
What happens is that Dbus starts at boot and queries LDAP authenticating as "messagebus". Since NSCD is not started yet, dbus has problems.
These are some more enlightening errors:
dbus-daemon: GSSAPI Error: Unspecified GSS failure. Minor code may provide more information (Credentials cache file '/tmp/krb5cc_101' not found)
dbus-daemon: nss_ldap: failed to bind to LDAP server ldap://<server>/: Local error
dbus-daemon: nss_ldap: could not search LDAP server - Server is unavailable
We must start NSCD before DBUS, then. Ubuntu 10.04 is using upstart for many services, including DBUS. Nscd is still relying on symlinks, so the startup order can't be modified easily.
The problem has been solved with a modification of the dbus upstart script and creating a custom Nscd upstart script, to make dbus depend on nscd. Briefly, something of this kind:
upstart dbus.conf modified line:
upstart nscd.conf new file
"start on started nscd"
"description "name service cache daemon"
start on local-filesystems
stop on runlevel 
mkdir -p /var/run/nscd
exec /usr/sbin/nscd -f /etc/nscd.conf"
I'm pretty scared about the maintainability of this solution, an update could break everything. At least, we got the cause.
I really don't know who should be contacted here, whether ubuntu devs, dbus devs or whatever!