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.
If you wish to "keep" the videos or pictures and also clear your iDevice, make sure you sync or backup your pictures in any way you choose before deleting.
The EASIEST way to delete All pictures and/videos is to attach your device to a MAC with an USB cord. Start the app "Image Capture" and select all content you wish to delete. Once selected, there is a delete function inside of image capture, choose this and all selected content on your iDevice will be deleted.
Best Answer
The places to check would be: