You are not the only one. It is the iPhone 5 which features a new bluetooth 4 platform as opposed to 2.1 for the iPhone 4s.
Make sure that your macbook is compatible with bluetooth 4.
iPhone 5 doesn't connect with MacBook Pro on Lion... but was fine on Leopard... Anyone knows the cause solution. Thanks