This is something people trip over all the time, even when they know about it. :-) You're seeing this for the same reason parseInt("1abc") returns 1: parseInt stops at the first invalid character and returns whatever it has at that point. If there are no valid characters to parse, it returns NaN.
parseInt(8, 3) means "parse "8" in base 3" (note that it converts the number 8 to a string; details in the spec). But in base 3, the single-digit numbers are just 0, 1, and 2. It's like asking it to parse "9" in octal. Since there were no valid characters, you got NaN.
parseInt(16, 3) is asking it to parse "16" in base 3. Since it can parse the 1, it does, and then it stops at the 6 because it can't parse it. So it returns 1.
So parseInt first uses toString on the first argument? That would make sense.
I suppose 123e-2 gives 1 since it turns into 1.23 first, and then parsing stops at the decimal point?
"This is something people trip over all the time, even when they know about it" -> am I the only one that thinks this should be a bug? Doing the same in Java for example will give you a NumberFormatException each time.
@SvenMarnach: That part of parseInt (coercing the first argument to string) makes sense. The purpose of parseInt is to parse a string to a whole number. So if you give it something that isn't a string, getting the string representation of it to start with makes sense. What it does after that is a whole 'nother story...