I can only guess, but the maximum size is 2048x2048 (iPhone 3GS, iPhone 4, iPod touch 3rd gen) and 1024x1024 (iPhone Classic, iPhone 3G, iPod Touch 1st gen, iPod Touch 2nd gen).

Well, the iPod Touch 1st gen and the iPhone classic aren't supported anymore, but it's better to use 1024x1024 as maximum (or increase the size of the binary and use 2048x2048 for the 3GS and iPhone 4).
Best should be to use as less textures as possible, texture switching is a expensive process and kill your framerate really fast. So you better go with a 1024x1024 skin instead of two 512x1512 skins.

However, those are my experiences with my engine (which is just 2D), so maybe Slin has made other experiences.