One more thing:

One thing I tried to do was "transplant" the java db files from my old phone onto the new phone (having figured out which set belonged to Google Maps), however, that didn't work.

My thinking was that there most likely is a boolean variable stored in a database file that determines whether the user has accepted the T&Cs or not. If it could be flipped then it may circumvent this issue (assuming it's a T&C download error? 404?)