I add my voice to yours: Only after running the 10.7.4 on my FileVault2 protected 15" MacBook Pro (2010) did I get the "Problems were found with the partition map which might prevent booting" error -- and can confirm that it corresponds with FileVault2
Here's a sequence of events that may help Apple (if they are listening) to diagnose this
1) The drive (and partition) passed Disk First Aid (DFA) testing prior to running the 10.7.4 update
2) I did my customary backup (clone using Carbon Copy Cloner, CCC) and updated (Combo) to OS X 10.7.4
3) A week later I ran Disk First Aid again (prior to doing another CCC clone and got the error listed above (and then performed my backup)
4) Booting from my clone, wiped and recreated the partiion on my MBP's internal drive, and installed Lion. DFA gave it a clean bill of health
5) After installing Lion, I cloned from my backup to my MBP's internal drive. Rebooted from the internal drive, and DFA again said all was well.
6) Activated FileVault2 again, permitted two of the three accounts to be unlockers. I let it complete, and rebooted.
7) It rebooted normally, and the ran DFA again -- and the error (which had not been present prior to initating File
Vault2 whole disk encryption) was back.
I have never had a problem with FileVault2, and conclude that one of the things that they fixed to permit peaceful coexistence with the original FileVault has caused this apparent problem.
Apple, please take note.