Hola
Cuando haces subrutinas de tiempo, éstas siempre están basadas en la velocidad del micro. Si haces una subrutina de tiempo de 1ms mediante ciclos en los que el procesador no hace nada y quieres aumentar la velocidad del procesador, esa subrutina se ejecutará en menos tiempo, es decir, 0.5ms en tu caso.
Si haces una subrutina mediante el timer que incluyen los AVR, también cambiará el tiempo resultante, esta vez dependiendo de que datos hayas cargado al contador del timer.
Definitivamente debes modificar tu programa si aumentas o disminuyes la velocidad a la que corre el micro. Pero ahora usando como base los 16MHz.
Si el tiempo que esperas que tarde tu ciclo es grande y aumentas la velocidad del micro, entonces el ciclo será más corto.