To the extent that Linux is technically just the kernel and fundamental services, Android uses Linux but is not itself "Linux".
To the extent that Linux implies "GNU Linux", i.e. a whole operating system and a broadly interoperable and source compatible set of *nix services, Android is not Linux any more than iOS is FreeBSD.
Then you could argue that any embedded device that runs the Linux kernel is not Linux because it doesn't use the GNU userland. I think its splitting hairs, anything that runs the Linux kernel is by definition, Linux. You can replace the GNU userland with anything you want, it doesn't suddenly make it a completely new operating system.
Sounds like the argument is a question of definitions - does "operating system" mean kernel, userland, or both? You argue that changing the userland doesn't change the OS. I could counterargue that Debian/kFreeBSD is the "same operating system" with a different kernel.
RMS believes that userland makes an OS, because he wrote a userland. Linus believes that kernel makes an OS, because he wrote a kernel. Calling Android "Linux" is like calling Windows 8 "Windows NT", i.e. correct if you're talking about kernels and wrong otherwise.
