Como bien te han dicho, convendría que fuera como mínimo de 1280x800, que es la resolución de la pantalla.
Por otro lado... la resolución no importa demasiado, ya que no es la foto lo que directamente va al fondo de pantalla, sino una copia en caché que android adapta a sus necesidades recortándola como tu le indiques cuando eliges el fondo. Si te das cuenta, al seleccionar el fondo no puedes cambiar las proporciones de lo que vas a recortar, ya que esas son las que android quiere.
Además hay que decir que el fondo no se va a ver con los mismo límites cuando estés en vertical que en horizontal.
Lo que te debe quedar claro es que las fotos que hagas no van a cuadrar nunca con el fondo de pantalla, ya que las proporciones son distintas.