Acceptable texture sizes should conform to a power of 2, ie 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024 and so on. Length and width do not need to be equal, thus a 256x512 texture would work.
Don't remember what happens when using a texture that does not conform.
MDA
Just to expand upon this...
Looking back through VERY OLD irc convo logs, what MDA says is very true; however, the textures should be incremental scalings of 8 based upon an 8-bit binary scale. Hence these sizes WILL work (along with any combo thereof):
8x8 - minimum recommended size
16x16
32x32
64x64
128x128
256x256
512x512
1024x1024 - maximum recommended size
The game engine is optimized for 256x256 and 512x512 mapping.
Furthermore, for odd shaped textures it is recommended that the larger axis never be more than 2x the size of the smaller axis (e.g. 256x512, 512x1024).