GPS won't work with Serial.begin

I tried.
I tried using the tinyGPS example, but I get nothing.
As a metter of fact - the only change I see when running the tinyGPS example is this:
If I play with the connection between the GPS's Tx and the arduino (taking it in and out) - I raise the character count by a few...
But no real info, and not when I keep it connected.

There might be ways to go around it, but I thought connecting a GPS is an everyday experience. I can't seem to find record of people expiriencing the problem I am having.