Have you tried port forwarding? Or temporarily connecting directly via the modem to see if it does connect ok? If it connects ok then the issue is probably with UPnP for your Linksys. After the reformat, did you re-enable UPnP? (though this should be on by default.) For port forwarding find your model (or similar) here http://www.portforward.com/routers.htm