Chris!
It looks like your other mailserver subscribes to the same blacklist.
I laughfed when most of Spain got blacklisted the other week, but beeing
in that situation is no fun at all :(
I hope that the good people at chello.se will soon solve the problem.
/jens