I have an iPhone 3GS that has a data plan and tethering enabled. It is running iOS 5.1.1
Being an iPhone it only does tethering over bluetooth and USB, not WiFi.
I also have iPhone 4, a 1st-gen iPad, and a year-old MacBook Pro.
I have been able to connect to the internet from the iPad to the iPhone 3GS over bluetooth (started System Preferences --> General --> Bluetooth on both devices, Paired the iPad with the iPhone etc.).
I have also been able to connect to the internet from the MacBook Pro to the iPhone 3GS over bluetooth (started System Preferences --> General --> Bluetooth on the iPhone, Set up a Bluetooth Device on the Mac, Paired the Mac with the iPhone etc.)
However, I cannot connect my iPhone 4 to the iPhone 3GS via bluetooth.
When I start up bluetooth preferences on both devices, they do not see each other. Since I cannot see the device, I cannot pair.
The iPhone 4 is also running iOS 5.1.1, same as the iPad.
Any reason why I cannot see or connect from the iPhone 4?