Few random thoughts/observations from a new user:
I was able to repeat sixchristoph's level of success using similar settings and ran into similar issues.
Not sure how well known NMEA data is but for quick reference try http://www.gpsinformation.org/dale/nmea.htm, on my test run it looks like it started out cycling through the following: (corupted line), GPRMC, GPVTG, (corupted line), GPGGA; this eventually settled to a fairly stable back and forth between GPRMC and GPVTG (kinda bummed, no altitude in those two but GPRMC has UTC time at least!). I'm assuming the number in front of the $ on these lines is the standard elapsed time from the previous data-point. I set my LOOP_INTERVAL to 500, looks like the datalogger waits ~500 ms then grabs data from the OBD2 and then imeadiately grabs a GPS read (my accelerometer is off, haven't bothered trying to turn it on yet) before waiting ~500 more ms.
Something to keep in mind, it can take a minute for a GPS lock to get established (at least this has been my experience with past gps loggers), I wonder if the errors/corupt lines I saw in the begining might be related to some sort of initial start-up cost. I haven't checked extensively but after the first few LOOP_INTERVALs of data the logger seemed pretty reliable, then at the end it powers off and sort of sputters for a few cycles with just GPS data points (I can work around that at least).
I also wonder if there is a way to specify/limit which NMEA sentences are retireved, and maybe change up how the loop/cycle picks datapoints to record.
I also had the problems where if I didn't start my car right away the logger wouldn't start logging (when I plug my logger in, prior to ignition, the blue light will go off for 3 cycles and then stop, When I waited past those three cycles the logger wouldn't start up on ignition). Likewise when I stopped the car and resarted later (without reseating the logger) the logger didn't start up.
Not sure if any of that helps, I'm a total Arduino newb, but I sort of know GPS/data.