While iPhone software/firmware update 1.1.4 fixed some serious Bluetooth issues introduced with version 1.1.3 -- including incompatibility with GPS units from Garmin (StreetPilot C550, Nuvi 360, 760, etc.), some integrated car Bluetooth systems and more -- it also introduced the inability to use Bluetooth at all for some users.
Fortunately, all the users we've spoken with who have encountered this problem had success with a fix we've mentioned before: Toggling Airplane Mode on and off. To do this, turn Bluetooth off, then navigate to Settings, then slide Airplane Mode to On, wait a few seconds, then slide it back to Off. It seems that discontinuing and restarting the EDGE and WiFi components in the iPhone can restore connectivity.