1.) Open up the MP4 in a hex editor (HxD is a freeware for Windows - be warned: it tries to automatically save a "backup" copy when saving, but that can be aborted)
2.) Search for the hex "61 76 63 43" ("avcC" in ASCII) - it should occur only once near the top
3.) The next byte after that is usually "01" and isn't important
4.) The next two bytes declare Profile ("42 E0" = Baseline, "4D 40" = Main, "58 A0" = Extended, "64 00" = High).
5.) The next byte declares AVC Level ("1F" = Level 3.1, "29" = Level 4.1, "33" = Level 5.1)
6.) Change whatever is in the AVC level to "1F" in hex and save. Try syncing the movie to the iPad again. (It would also be a good idea to check to see if you are violating the AVC 3.1 limits by doing so.)