Never had roads disappear like tide15 mentioned...are you using any mods?
As for the actual cause i am inclined towards Shaglio's explanation if it is a legitimate game issue and the reason why i never rely on roads going through territory i don't specifically own even if it means going a longer route.
I notice you did say you have to reload the game to solve the issue, are you using any mods or are two parts of your empire connected by a harbour...as barbarian ship or a ship you are at war with could be blockading your harbour occasionally?