None of my longish CAT5 cables would work at 1GB/s. Having a day off I am fixed a few loose ends at home, one being those pesky cat-5 cables. After following this image found on Wikipedia the two cables now work perfectly:

The order of the wires is very important. Of course I learned about twisted pairs in high-school. I just assumed that like colors go together in pairs, but it is not the case for Cat-5 at least.

Hopefully this helps someone out there for the same frustration I had - are maybe everyone else reads instructions? It is also worth pointing out that Cat-5e is fine for TBase1000and is a documented IEEE standard: http://en.wikipedia.org/wiki/Category_5_cable