I'm using hal 0.5.11-8 on an Eee Pc 701. I get the same error mentioned in the OP, except none of the fixes here do anything. Looking at the output of strace -f /var/sbin/hald reveals that I don't appear to have a directory of file @ /var/cache/hald/fdi-cache...
ls on /var/cache/hald reveals that there is a fdi-cache~ though... Any help/suggestions...???