I always create textures in PowerPoint (I know, strange, but the Scifi elements you can make...PHWOAR) and copy them into Paint.NET as 512x512. I know it's not a great resolution but then it's more quality than resolution (I refrained from using
size there in case of an innuendo joke

) and the textures I've made look pretty decent.
Normals maps usually gives the texture more of a bigger looking resolution, dependant on what is consistent on the normal map (in UDK I always implement Detail maps into the normal, and if I could get X10 working and the shaders rendering I could try it in X10). But it basically depends on what the texture is for.
I've never known FPSC to shrink textures either, the texture options are High(no reduction), Medium(2x reduction) and Low(4x reduction) so it may be one of the settings that is toning down the resolutions

.
-SSG