Yes, it is possible. I have Ubuntu 11.04, NetworkManager 0.8.4, Android Nexus One phone running Cyanogenmod 7.
As described by Roman, right-click on the NetworkManager icon and choose "Create new wireless network". I chose to leave the connection wide open (no WPA, no WEP). My phone was able to see the network right away and I connected without trouble. The bridging was automatically done so I could browse the internet without configuring anything extra.
The reason why you having trouble with the above method is because stock Android 2.3 doesn't support ad-hoc networks. To be precise, Android's wpa_supplicant does not show ad-hoc networks. There are a number of ways to fix this. Google around and go hunting in the xda-developers forums. You will probably need to do some hacking on your phone that is beyond the scope of this answer.
My personal recommendation: if your phone supports Cyanogenmod, you can install it to get ad-hoc support and other hackish delights. You will need to root your phone, which may or may not be to your taste.
Another alternative is to try "Infrastructure mode". After setting up the ad-hoc wireless network as per above, click on the NetworkManager icon, choose "Edit connections". Hit the wireless tab and Edit the ad-hoc network you just created. Under Mode, choose "Infrastructure". I am unsure if this will work for you since I don't have a stock Android phone to test with. My thought is if ad-hoc mode is the problem, then the another mode might be the solution.
Good luck!
You have to set the phone up as a wifi hotspot then connect your laptop to the SSID of your phone. On my Android phone (4.1.2), I go to Settings, Wireless and Networks then mobile network sharing. Then I can enable the portable wifi hotspot.
You can probably get a more detailed answer here: https://android.stackexchange.com/
Best Answer
On modern android phones, the simplest way to do this is to make a wifi hotspot with your phone and connect to that.