I suspect it's more related to the connections at the 8500. And since you can't hook it up to a regular POTS line, that tells me you don't know if it's worked successfully on one before, hence my guess that it's a setup issue on the 8500.
It has two ports - LINE and EXT. Make sure the phone cord from the wall is in the LINE port. The EXT port is for the phone line that goes to a phone so that you can share the line.
If that's ok, then check to make sure you are set on TONE, not PULSE to dial.
If both those are ok, you can monitor the dialing by connecting a phone to the EXT port to see whether it gets the dial tone and then tries to dial, and if in doing so the dial tone goes away but for some reason the number doesn't get dialed correctly.
If you are still having issues, use the Fax Setup guide and make sure you follow the steps. There is a Fax Test in there as well. You should have this guide since I'm assuming you got this printer new.
http://h10032.www1.hp.com/ctg/Manual/c01696942.pdf