I had a similar problem on a regular Android tablet (so not sure if the Gallery on the Samsung is the same as Photos on the Kindle) but this forced a refresh without waiting or plugging in USB
sendBroadcast(new Intent(Intent.ACTION_MEDIA_MOUNTED, Uri.parse(
"file://"+Environment.getExternalStorageDirectory())));
I will try and confirm that it works on the Kindle Fire HD over the weekend