Clearly, for new cable runs, I'd pick CAT6. However, I have a 1000 foot spool of CAT5e, so there won't be any CAT6 here for some time.

As long as all 8 wires are intact, CAT5 will run gigabit just fine for runs in the 40-50 foot range, longer runs may run into a problem. However, I've run gigabit for 500 feet using CAT5e (yes, I know that's out of spec), and it worked just fine. I don't recommend exceeding 300 feet for any single hop, but it can be done.