Well, it is on a T1 line - so that is why they made the changes. I thought it looked like everything was winding up at my name servers as well, yet the PTR records are not being found.
How about the results of the dig I did on my IP, isn't that wrong? I don't know this stuff very well yet, but it said:
";; ANSWER SECTION:
xx.255.167.12.in-addr.arpa. 42424 IN CNAME xx.xx/xx.255.167.12.in-addr.arpa."
It has no mention of an actual domain name, is that a bit of a clue as to what is wrong?