You can initiate pairing from any computer.
Limit your Arduino sketch Serial communication speed to 9600 baud. This step is very important, if you try other baud rates the Android device will not be able to communicate with the Bluefruit EZ-link.
The Mac bluetooth core sometimes doesn't fully release the bluetooth connection state as fast as we'd like. Wait a few seconds and try again!
Wireless just isn't as fast as wired. For example, with USB 'wired' data, the data is just 'sent' because the wire is trusted. With wireless/bluetooth, there has to be a lot more layers of checking and verification because there's no way to know if it was received and its suscepitble to noise. You can try to speed up by unchecking the Verify Firmware box in the Prefs of the Arduino IDE, that should cut it in half...but of course adds some risk!
Make sure you do not have any extra Bluetooth drivers installed. In particular, make sure you don't have CSR/Harmony bluetooth drivers or any other non-Windows-native bluetooth stack. You should be using ONLY the native Windows bluetooth! Unpair the EZ-Link, uninstall any other drivers and reboot, then re-pair. For more details check out this forum thread: