How to resolve error: "Couldn't modify partition map because file system verification failed"?
OK, this isn't too bad. Reboot while holding Command ⌘-S to enter single user mode. When it gives you a prompt, type
fsck -fy
then press return. it will repair your disk. When it's done, type
reboot
and try partitioning again.
The solution ended up being to create a Lion install disk, boot from the disk, run disk utility repair on the drive and volume, then resize the partition. Easier than I thought it would be.