@Rohan:

Did you set the phone as your default device in the control panel? I'm pretty sure that's what maemo-pan tries to connect to. That's the only thing I can think of off the top of my head.

Also, like jhoff80 mentioned in response to someone else, make sure you run the Internet Connection Sharing app on the phone. I think it's buried in the windows directory w/ wm 6.1, you'll have to look up the app name somewhere else. (Sorry, I use wm5)