Very good posts firearrow. I hope you stick around. We always need more people like you here.
For the rest of you: Note that there actually
is another invariant. If we consider 1+1-dimensional proper and orthochronous Lorentz transformations, for p^2>0, the sign of p^1 is invariant. And even if there had been no other invariants (or if you were just ignoring this invariant because we're not interested in tachyons) evilcman's question was still a good question to ask.
The key to understanding these things is to understand that a
group action on a set partitions the set into "orbits". In this case the set is \mathbb R^4, and the orbits are defined as \mathcal O_p=\{\Lambda p|\Lambda\in SO(3,1)\} for each p\in\mathbb R^4. Note that if p'\in\mathcal O_p, then \mathcal O_{p'}=\mathcal O_p. From this it's easy to see that each p belongs to exactly one orbit.
Let's focus on SO(1,1) again. When we discover that p^2=-(p^0)^2+(p^1)^2 is invariant, we know that each orbit must be a subset of a hyperbola, but we don't know
which subset until we have noticed (as firearrow mentioned) that the group action restricted to a branch of one of these hyperbolas is
transitive. "Transitive" means that for each p and p' on the branch, there's a \Lambda such that p'=\Lambda p. If we consider a specific p with p^0>0, then transitivity on the branch p^0=\sqrt{(p^1)^2+m^2} is proved by the fact that we can choose \Lambda to give (\Lambda p)^1 any value.
Now what
that means is that we have completely determined the orbits of SO(1,1), which is what we're really interested in. This is much more interesting (to a physicist) than finding all the invariant
functions, because it's a huge step towards finding all the irreducible representations of the group.