I usually default a new document to 4096 x 4096px, mostly because that's the size at which I do most of my texture painting. I'll commonly crop it down from there, though; I like having some nice margins for slop-over.

Jax: Keep in mind that you can't actually print 8.5 x 11" unless your printer can print edge-to-edge. Try designing at 7.5 x 10" instead and see if you can get a correct print that way (1/2" margin on each side. Most consumer printers should be capable of that.)