This issue is related to issue13158 which deals with a GNU tar specific extension to the original tar format. In that issue a negative number in the uid/gid fields caused problems. In your case the problem is a negative mtime field.

Reading these particular number fields was fixed in Python 3.2. You might be able to read the archive in question with that version. You should definitely try that.

Besides that, I was unable to reproduce the error you report. I just did some tests and could not even open my test archive, because it was not recognized as a tar file. I didn't come as far as the os.utime() call.