Para resumir la información relevante, permítanme citar de la Q&A que eldarerathis enlazó arriba (todos los créditos van para él, ya que esta es su respuesta):
Un archivo .dex es básicamente una versión de bytecode compilada de una aplicación que ha sido construida para la Máquina Virtual Dalvik en la que se ejecutan las aplicaciones de Android. Creo que es una abreviatura de Ejecutable Dalvik, pero no estoy seguro si lo estoy recordando correctamente.
Un archivo .odex es un archivo .dex optimizado (de ahí la 'o'), lo que significa que básicamente ha sido precompilado para una plataforma específica. La ventaja de esto es que el tiempo de arranque es mucho más rápido ya que la VM no tiene que realizar ninguna optimización en el arranque/ejecución. Las desventajas son 1) que ocupa algo de espacio adicional y 2) una aplicación con extensión odex no se ejecutará correctamente si se coloca en otro dispositivo, y debe tener el archivo .odex asociado para ejecutarse en absoluto.
Cuando instalas una aplicación, Android analizará el archivo .apk y configurará la caché de Dalvik del dispositivo con una versión optimizada de su código, por lo que la aplicación se iniciará y ejecutará más rápido (después de un restablecimiento de fábrica de tu dispositivo, lo hace para todas las aplicaciones preinstaladas, e incluso para todas las aplicaciones de usuario, después de borrar la caché de Dalvik, lo cual es posible desde el menú de recuperación con la mayoría de las CustomROMs, por eso la primera arrancada tarda mucho más que las arrancadas posteriores).
Sin embargo, cuando se encuentra un "odex", simplemente se copiará en la caché de Dalvik. Como señaló eldarerathis, el archivo .odex se construyó para hardware específico (me recuerda al Assembly) - por lo que si ese "hardware específico" no es el que utiliza el dispositivo actual, seguramente tendrás problemas.
