PXO is working fine for me now.
I suspect I know the real cause for this. Playing without a valid fs2open_pxo.cfg config file in both Freespace2\Data and Freespace2\Mediavps\Data.
You should have that file in both folders and if you open it up in notepad it should say
fs2netd.game-warden.com
12000
If you don't have one just make a new text file, name it correctly and copy it into both folders.
Turey : If your installer doesn't do this already you may want to consider doing it until the new mediaVPs come out (at which point you'll only need the Freespace2\Data one most likely).