1024x1024 is about the safest you can go on any device, especially on older ones. Newer devices shouldn't have any problem, although I've seen recent devices (I recall a Galaxy Nexus, the newest ICS update fixed that though) render white quads with texture sizes of size 2048x1024.
If you're targeting new devices and want to keep older ones compatible, it shouldn't hurt to split your tilesets. After all, you aren't likely to do too many context switches if you use two or three spritesheets for background, etc.
与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…