Gallery problem:
After the first time's "No photos or videos found" I did start the gallery some times later, with success
Maybe the phone needs some time to rescan the SD card
Also you might try 'SDrescan', free in Market/Play Store.
Depending of the amount of files in your gallery the app might need some time for scanning.
Harry