Same here on Mac OS X. Phex worked great, had to switch to 56K modem during 3 months, came back to 10MBit connection, upgraded to Phex 0.7.3 and downloading has become totally impossible. I get lots of "connection refused" messages too; sometimes it connects, but after a few seconds the host disconnects. I tried changing the network settings but nothing helps.
I have managed once to get 4 search results by searching for the word "something", maybe this was due to a bug in the bug which prevents getting a decent connection?
Sigh, back to the disgusting LimeWire, at least it works.