Are half of all numbers odd?
The basic problem with your argument is that the concept of half of an infinite set is not well-defined. It’s possible to pair up the even integers with the odd integers with none left over in either set, and if we were talking about finite sets, that would be a demonstration that each was half of the whole set of integers. However, it’s also possible to pair up the multiples of $100$, say, with all the rest of the integers with none left over in either set, and the multiples of $100$ are obviously only part of the set of even numbers. Clearly, then, this kind of pairing argument cannot lead to any very useful notion of half of the set of integers.
There is a notion of asymptotic density of a set of positive integers that does a pretty good job of capturing many people’s intuitive sense of what half (or any other fraction) of the set of positive integers should mean. Let $A\subseteq\mathbb{Z}^+$; for each $n\in\mathbb{Z}^+$, $$\frac{|A\cap\{1,2,\dots,n\}|}n$$ is the fraction of the first $n$ positive integers that are in the set $A$. If this fraction approaches a limit $\alpha$ as $n$ increases, i.e., if $$\lim_{n\to\infty}\frac{|A\cap\{1,2,\dots,n\}|}n=\alpha\;,$$ the set $A$ is said to have asymptotic density $\alpha$. (Note that the limit need not exist: not all sets of positive integers have asymptotic densities. It’s not hard to show that if $A$ is the set of even integers or the set of odd integers, its asymptotic density is $1/2$, so it’s meaningful to say that each of these sets comprises half of the positive integers in terms of asymptotic density. Similarly, for each positive integer $n$, the set of multiples of $n$ can easily be shown to have density $1/n$, exactly as one would wish.
Added: In the comments Srivatsan points out an excellent example: the perfect squares can be paired up one-for-one with the integers, but their asymptotic density is $0$: they get sparser and sparser as you get further away from $0$. Thus, in one sense there are just as many perfect squares as there are integers, and yet in another sense almost every positive integers is a non-square.
While they are both countable, there is a more applicable mechanism for measuring how many natural numbers have a certain property. If $A \subset \mathbb{N}$, let $$A_n = \text{number of elements in A less or equal to n}$$ then we can define density of $A$ as $$\operatorname{density}(A) = \lim_{n\to\infty} \frac{A_n}{n}$$Then the odd numbers have density $\frac{1}{2}$.
It's already mentioned in the comments that you will encounter some problems when talking about half of the elements of an infinite set. There are ways to compare the size of infinite sets.
See: http://en.wikipedia.org/wiki/Cardinality
Two sets have the same cardinality (=size), if there exists a bijection between them. The natural numbers and all other sets with the same cardinality are called countably infinite. That means roughly that we can find a way of enumerating them (and additionally they are infinite). It is easy to give a bijection from the natural numbers to the even numbers. Just associate to a number $n$ the even number $2n$, so we conclude that the cardinality of the even numbers is the same as the cardinality of all natural numbers! The same is true for the odd numbers, so in set theory the two sets you want to compare are considered equally large!
That being said, there are other notions of size for sets of natural numbers. One of them is natural density: http://en.wikipedia.org/wiki/Natural_density
Instead of "counting" all even numbers at once you restrict the set of numbers you look at to natural numbers $\leq n$ and calculate the proportion $x_n$ of even numbers in this set. $$x_n =\frac{\text{even numbers below }n}{n}$$ The density is then defined as the limit of the $x_n$ and you will find that it is indeed $\frac{1}{2}$, just as the natural density of the odd numbers.
There are many interesting theorems about the densities of certain subsets of the natural numbers like Dirichlet's theorem on primes in arithmetic progressions. One instance of the theorem tells us for example that "half of the primes are congruent to 1 modulo 4 and the other half is congruent to 3".