Tiene pinta de que tu APP (por el motivo que sea, incluso las primeras versiones de WhatsApp después de aparecer no eran compatibles) no es compatible con ART.
¿El móvil 5.1 donde lo estás probando por casualidad es un Samsung? Samsung en (su mayoría) de dispositivos con 5.0 NO disponen de la opción de usar ART, teniendo que usar Dalvik si o si, y en los que traen 5.1 Dalvik es por defecto y ART es opcional (Teóricamente ART debería ser la opción por defecto desde 5.0, pero en Samsung no es así, al menos con ROMs oficiales, precisamente porque su TouchWiz no es compatible con ART)
Así que yo apostaría a que estás probando la app en un 5.0 en un móvil NO Samsung (O sin ROM oficial) y la 5.1 en un Samsung con ROM oficial.