The speed you see on the datasheet is the maximum.
The core code must be told the actual speed that the part is running.
The speed you tell the code doesn't modify the actual speed it merely
tells the core code what the speed is.
This is why they must agree.
If things are now working when you are telling the core code that the AVR
is running at 16Mhz, it must be running 16Mhz rather than 8mhz.
Are you sure the board you have was running 8mhz?
--- bill