Have you tried loading and running other programs to see how they perform? Is it a problem with that one program or the mega? It would be almost impossible to 'accidentally' change the fuses but you have said that clearing and setting the interrupts has an effect. It would be useful to see the code that causes this otherwise it's just wild speculation.