Never size up (unless you are going to re-do it),
but ALWAYS size down to as small as acceptable.

I always paint textures on a 1024X1024 canvas and scale down to whatever size I need for the given model. It allows me to put more detail in.

Same goes for Normal mapping software.