Have you tried the old computer at a different location plug.
are you accessing it wirelessly or through a cabled connection?
Since you replaced the computer and replaced the ethernet cable, I'd start looking for interference and at the connections on the outlet and patch panel.
Get yourself a http://www.newegg.com/Product/Product.aspx?Item=N82E16899997006 if you don't already have one. Test a couple cables, then plug one into the wall outlet, then another into the terminating end of the patch panel. Connect the remote tester on one end, and testing unit to the other. Since they are most likely quite far away, you'll most likely want to test multiple times.
No I have not. That's probably a good idea. Not actually there right now though.
Cabled. What's weird is I can remotely control it and see when the pings succeed and fail, but i'm still connected... But I have gotten kicked off a few times...
Are you using any switches or is it a hub. If it is a hub that could could explain the network connectivity since a hub can get overwhelmed in traffic. It can also be a port on the hub or switch that is starting to fail. So you will want to test them all.
Also you want to use the tester that one of the posters suggested to rule out a cable being faulty.