Cat5e is needed (over Cat5) for 1000BASE-T because of changes which result in lower crosstalk. 100m is the maximum run. While I haven't used Cat6, it appears to be a slightly larger gauge and, is actually
certified for 1000BASE-T. Although for most installations (especially shorter runs).
Cat5e should be fine unless it's a long run (>100m) and/or an especially noisy one, (it's rated for up to 350GHz). Lower noise environments would be good for either (plan cable routing as best you can).
The
article I'm referencing also says if you are or intend to use 1000BASE-T, and all components in the network are rated for 1000BASE-T, it might be worth getting 6.
You didn't say what the slowdown speed actually was and if the NAS was RAID or?; also all interfaces: routers, switches, iNICs, etc all need to be rated for 1000BASE-T.