No creo que este sea su problema, pero podría ser y no parece haber sido planteado en otro lugar. Compré una nueva MacBook Pro con Lion hace unos meses, y descubrí que el (también nuevo) Magic Mouse no se conectaba automáticamente, tuve que forzarlo a conectarse después de cualquier desconexión por apagar el MM o reiniciar la MacBook.
Uno de los genios del Genius Bar, después de una hora de experimentación en ½ y en el proceso de decirme que Lion tendría que ser recargado, de repente se dio cuenta de que el MM se conectaba al ser pulsado. Declaró que no se había encontrado con esto antes y que debe ser una nueva característica en Lion relacionada con la preservación de la batería.
En resumen, intenta un solo clic de ratón para iniciar la conexión Bluetooth.