first, make sure you do the size change in one move. Every time you drag a corner, the program renders the picture over again and will quickly make words and small details turn into a blurry mess. Also, make sure you are keeping the horizontal to verticle ratio the same(ie keep it in proportion). If you're stretching or shrinking one dimension more than the other, you'll definitely have clarity problems.
The second option is don't use photoshop to shrink the pic. Use a program like printshop and import the pic at full resolution after you have set up or loaded the template. That way the pic will only be redrawn one time.