Nunca he experimentado esto en Safari, y espero que haya algún tipo de acceso directo conflictivo. O eso, o "con bastante frecuencia" el foco de su mouse está en Flash o Java, y los accesos directos no se envían al navegador (lo que no parece muy probable dada la frecuencia).
Debido a que me cambié a Safari después de varios años seguidos de usar Chrome y Firefox, he establecido los comandos de la pestaña Anterior / Siguiente en ⌥ + ⌘ + ← / → , usando las Preferencias del sistema. Una vez más, nunca he tenido problemas con el cambio, por lo que sugeriría (si está dispuesto y no puede encontrar la fuente del problema) configurar otro atajo que pueda recordar.