Atmega8 cbi/sbi Timing Issue
After a bit of troubleshooting I found the answer. 

I was seeing quite sporadic behavior with regards to timing. Sometimes i would get the correct timing of 62.5ns and sometimes not.

After eliminating all the possibilities, It had to be the crystal. 

Replacing the crystal solved the issue. All the timings are now correct