I've resolved the problem, and it wasn't pretty.
It starts with iPhoto 8 ('09) on my iMac. This library had a bunch of "referenced" photos, ie, photos whos image files were outside of the iPhoto Library folder. In iPhoto 8 this was handled by creating an OS X alias file in the Originals folder within the iPhoto Library folder.
Then I wanted to move my library to my new MacBook Air running Lion and iPhoto 9 ('11). Forgetting that I had referenced files in my library I just copied the iPhoto Library folder from my iMac to my MacBook Air as the Apple support docs say (they don't mention anything about referenced files). Of course the referenced files were not copied to the MacBook, but everything appeared to be OK.
Start iPhoto 9 on my MacBook and it upgrades the library. It can't find the referenced images of course, but there's no warning or anything. iPhoto 9 has a totally different folder and database structure. All the information it needs about where to find an image is now in the Library.apdb SQlite database file in iPhoto Library/Database/apdb/. In that db there's a table called RKMaster which stores the info about each photo. RKMaster has a column called imagePath which is where the full path of the original image file is supposed to go. However, since my referenced images were not available during the iPhoto library upgrade it just set these all to Masters/<image file name>, and stored the alias information from the iPhoto 8 database in a BLOB column called fileAliasData. When I worked out the referenced files were missing I copied them over to my MacBook, and the iPhoto was miraculously able to find them again because of the information in the fileAliasData column in the database.
However, iTunes and other apps that link to the iPhoto library don't access the iPhoto Library database directly. They use a file called AlbumData.xml in the iPhoto Library folder. iPhoto 9 re-creates this file every time you close iPhoto. Unfortunately, what it uses to build the full image path for putting in the XML file is what's stored in the imagePath column in the database, which by now is basically garbage. iPhoto can see all the files OK, but nothing else can.
The only solution was to painstakingly fix the RKMaster records for all my referenced files so that they pointed to the correct place. I took the opportunity to copy the files to the iPhoto Library folder in the process so that now all my images are in the iPhoto Library folder. This implied setting fileIsReferenced = 0 and fileAliasData = null for those records aswell.
Now I finally have everything working again, but it was a very long and tedious process that can only be done with some knowledge of SQL databases. Apple should really warn people about this potential problem when advising on how to move your iPhoto Library.
Best Answer
Download iPhoto Library Manager and use its rebuild function. (In Library Manager it's the FIle -> Rebuild command)
This will create an entirely new library. It will then copy (or try to) your photos and all the associated metadata and versions to this new Library, and arrange it as close as it can to what you had in the damaged Library. It does this based on information it finds in the iPhoto sharing mechanism - but that means that things not shared won't be there, so no slideshows, books or calendars, for instance - but it should get all your events, albums and keywords, faces and places back.
Because this process creates an entirely new library and leaves your old one untouched, it is non-destructive, and if you're not happy with the results you can simply return to your old one.