Mem,
I took the 5 sentences you posted and ran them through TinyGPS -- it's easy to do this by editing the testgps1 example -- and they all pass the checksum test. But they don't provide any data. I did a little debugging and finally noticed that the $GPRMC sentence is reporting V ("void") (term #2), which according to one page indicates "navigation receiver warming". This field must be "A" for TinyGPS to recognize it as valid. Also the $GPGGA sentence reports position type of "invalid or not available". The $GPGSV and $GPGSA sentences are checked for valid checksum, but no useful data is extracted.
http://ssro.ee.uec.ac.jp/ssro/uchuu-tsuushin/gps/GPS-data-format.html
Thanks again,
Mikal