Go to the Texture menu, not the one in the tools but the one in the file menu up top. Change the size for your texture map there.
There is a plug-in for quick and easy texture sizes found here.
You can see what menu I am talking about on this page cause the plug once downloaded will be found there. It is a great plug-in which is in the 3.5r3 version.
http://www.zbrushcentral.com/showthread.php?t=49728
I usually make the texture size thus creating a new texture and then select texture off then go back to the tools/texture sub pallet and hit the col to texture button. It will create a texture with the poly paint on it the last size you had a texture assigned to. Hope this Helps. 
here is the wiki page, to better describe what you need to do and yes you need the UVS assigned in the Tools/texture sub palette or make your own.
http://www.pixologic.com/docs/index.php/Baking_PolyPainting_into_a_Texture_Map
3.5 had some major changes for P.C. from 3.1… the Mac 3.2 looks a lot like the 3.5r3 that we just received at least that menu does. Interesting some things ours just got you’ve all had, I didn’t know that. Been thinking of getting a Mac…