Usually XT is for 4MHZ. I heard some lazy crystal (not resonator) may work better with HS but... there's certainely something better to do prior using HS fuse... well... as now i never have any problem with any 4MHZ crystal i use, and always set XT fuse for that. So is this because of the HS fuse? Maybe yes maybe no. It's sounds to me a bad crytsal or PIC start-up for sure but why? Bad capacitor, bad crystal, HS fuse. The only thing i can suggest is to set to XT and test it. Same problem? Could also be caused by a slow start-up power supply... Power-up timer fuse 'may' help.