Boggle. Seems like 1/2 the posts in here are about this same problem, yet people ignore the answers
The DNS seed nodes that the protoshares client uses are crap, so you have to use addnode.
either do it in your .conf file, addnode=xx.xx.xx.xx
or do it from command line, protoshares addnode xx.xx.xx.xx onetry and protoshares addnode xx.xx.xx.xx add
or do it from the -qt client from the terminal window, addnode xx.xx.xx.xx onetry and addnode xx.xx.xx.xx add
the real problem is that too many people don't allow incoming connections, thus there is a shortage of nodes that have open slots for incoming connections
reason for new wallet not mining was stated above. use a pool