I've just moved from Ubuntu (where bluetooth NAP worked (with the gnome bluetooth stuff at least)) to wheezy.
I thought that perhaps I was missing something, didn't have something setup right, etc. because when I try to connect using blueman I get the exact same error messages as the original poster. My phone isn't an iPhone, it's android based (HTC One X). So I'd guess that the issue isn't specific to the device you're connecting to.
