Simply replacing .bin with .tar.bz2 is not enough, for NDK releases older than 10b. For example, https://dl.google.com/android/ndk/android-ndk-r10b-linux-x86_64.tar.bz2 is not a valid link.
Turned out that the correct link for 10b was: https://dl.google.com/android/ndk/android-ndk32-r10b-linux-x86_64.tar.bz2 (note the additional '32'). However, this doesn't seem to apply to e.g. 10a, as this link doesn't work: https://dl.google.com/android/ndk/android-ndk32-r10a-linux-x86_64.tar.bz2 .
Bottom line: use http://web.archive.org until Google fixes this, if ever...