I got my recovery partition back! All I did was boot from an install disc (made from the Lion installer app), choose to install a fresh copy of Lion on the drive (without erasing anything first), and basically walk away from my Mac for about a half an hour.
When I returned to it, I was expecting dialogs for setting up a username, etc, but it was just the log in screen. I logged in, thinking I must have missed some important prompt and that I'd have to reboot from the installer again.
However, Find My Mac works now, as well as FileVault. I thought I would be spending the evening waiting for my data to restore from the Time Machine backup, but everything else is still intact. It's like the installer just "fixed" the current Lion installation.