trying making your texture tile at 128x128 pixels. This should give you a useable seamless tile (depending on your design)and assuming your background is divisible by 128 (height and width). Are you creating this from scatch? PS has some great default textures for tiling or you may be able to find free textures on the web.
If your design becomes too small, create a larger canvas, but make sure to keep it divisible by 128. (ie 256x256) or larger.