¿Android funciona con Linux?

Android ejecuta el Kernel de Linux para el sistema central y puede ser (y es) optimizado para varias plataformas (compilado para ARM, x86, x64, PPC, etc).

Aquí tienes un fantástico gráfico que te lo demuestra:

Fuente: Publicar en Unix.SE

Android se basa en la versión 2.6 de Linux para los servicios centrales del sistema, como la seguridad, la gestión de la memoria, la gestión de los procesos, la pila de redes y el modelo de controladores. El kernel también actúa como capa de abstracción entre el hardware y el resto de la pila de software.

Fuente: http://developer.Android.com/guide/basics/what-is-Android.html

Y mi comentario sobre tu segunda frase es que el Kernel de Linux no está pensado sólo para sistemas operativos de escritorio. Sus casos de uso varían desde sistemas operativos de escritorio a servidores, mainframes y supercomputadoras a dispositivos integrados.

Linux es un núcleo de sistema operativo ampliamente portado. Debido a su bajo coste y a su facilidad de personalización, el núcleo de Linux se utiliza en una gama muy diversa de arquitecturas informáticas: en los dispositivos de mano y en los sistemas mainframe, en dispositivos que van desde los teléfonos móviles hasta los superordenadores.

Por otro lado, Palm (posteriormente adquirida por HP) utiliza un sistema operativo derivado de Linux, webOS, que se emplea en su línea de smartphones Palm Pre. Varios cortafuegos y routers de fabricantes como Cisco/Linksys utilizan un kernel linux personalizado. Hay montones de dispositivos que utilizan Linux integrado.