Figured it out
This is definitely a bug in Touchwiz. If the app has been moved to SD and then updated after the move, the Icon disappears after a re-boot. If you move the app from SD to the phone and re-boot the icons stay. Move the apps back to SD and you are fine.
Touchwiz see the icon as an ID and links the icon to the folder if the folder moves Touchwiz assumes that the program is no longer there. By moving it to the phone the id is reconnected and then moved with the transfer to SD.
No need to reset completely, just remember to reboot the phone AFTER you move the programs from SD to Phone. Then reboot AGAIN after you move them back to SD.