I get coordinates but they are waaay off.
Have you tried printing the entire string to make sure all of the fields are present? How about pasting the actual string into your post.
I have seen some receivers that leave out some of the stuff. (They just put successive commas without any digits for some of the items, so actual positions of some meaningful fields in the string may be different.)
I get stuff like this:
The TinyGPS library seems successful in being able to parse lines with empty fields (at least it works for me with an EM-406A module).
Now, assuming all of the fields that you need are present and are in the expected place in the string so that you can actually get the latitude and longitude numbers from the receiver:
Shouldn't you be checking character 42 in your array (the Fix Quality) and, maybe, characters 44 and 45 (Number of Active Satellites)? I mean, a GPS receiver will spit out messages every second, regardless of conditions. You have to check to see whether they are meaningful, right?
What values, exactly, are you getting for the latitude and longitude items? What is your actual latitude and longitude?
Current Arduino libraries will print floats without the special function in your code. You can reduce source code clutter by just calling Serial.print for your floats.