If the photos were synced to the iPad, the only way to remove them is to sync an empyy folder in the Sync Photos From drop down menu of the photos tab in iTiunes or to uncheck the Sync photos box and follow that with a sync. If you don't have enough room to sync, you have to delete any other content to make the room so that you can complete the sync. Start deleting videos or TV shows, which are the biggest storage hogs, and then download them again after you can remove the photos when you sync.
If you store those items in iTunes, just sync the, back again. If you have no videos or TV shows, you will have to delete apps, music, books or anything else that you can, in order to make room.
So it's not really a Catch-22, you can delete anything in order to make room. It just involves more work than simply deleting photos in one step.