I have no problem making a connection (iPhone 4, original iPad) with the app I use (PhotoShare). The trick is, you have to connect using the in-app process, and the app has to be on screen on both devices. As soon as you switch out of the app, the connection is broken. I believe that's a "feature" of the PAN (Personal Area Network) Bluetooth profile, or at least Apple's implementation - seems like a good security practice (no connections left open accidentally or surreptitiously).
If you leave the app open on one device and you go to Settings > General > Bluetooth on the other, you will not see your other iOS device listed. This is expected behavior. The way I look at it is, it's the programs that are pairing over an established network, not the iOS device per se.