Back to Zabbix 1.4.6
I failed to get both Autodiscovery or even adding a host to the Zabbix monitor working on 1.5.6 so I decided to roll back to 1.4.6 afteral.
At least autodiscovery seems to work there.
The weird thing is that people upgrading from older versions seem to get it working like a charm, but a fresh install on a Centos 4.X seems to be troublesome, Just no time to debug it now.