Why doesn't Cantor's diagonal argument also apply to natural numbers? In my understanding of Cantor's diagonal argument, we start by representing each of a set of real numbers as an infinite bit string.
My question is: why can't we begin by representing each natural number as an infinite bit string? So that 0 = 00000000000..., 9 = 1001000000..., 255 = 111111110000000...., and so on.
If we could, then the diagonal argument would imply that there is a natural number not in the natural numbers, which is a contradiction.

If you represent a natural number as an infinite string, the string will become identically $0$ after a certain point.  If you think it through, the "diagonal argument" in this case doesn't produce a natural number; it will produce a string with infinitely many $1$s. 
On the other hand, you can consider possibly infinite binary strings --- i.e. strings in which there can be infinitely many $1$; this is one way to think of
the set of $2$-adic numbers, which 
is indeed an uncountable extension of the set of natural numbers (as one sees using the precise diagonal argument that you suggest).
