I have to believe that you have a wiring issue with the cables. The fact that you're redoing cables seems to be a red flag.
There is no difference going from CAT5 to CAT5e or CAT6 except better quality cable. If it works on CAT5, it will work on any better cable.
CAT5 Cable Wiring Diagram
HOW TO MAKE YOUR OWN CAT 5, TWISTED-PAIR NETWORK CABLES