Did you post all your code? For some reason people don't want to post an entire program, only the part they think is relevant.
I've got to wonder if you aren't running out of resources, since when it seems to work better when you remove code (tinyGPS).
You may think about using 4800 baud since you're using software serial. I noticed your code snippets changed from 4800 to 9600.
-j