I've had a few issues around this I might be able to help with, but as a disclaimer, I don't use NetworkManager on Ubuntu, and I'm on 8.04, not 8.10, so this might also not apply to you...
1) my ppp connection comes up as "disconnected", but my wireless and wired connections work - Outlook can find the HTTPS/RPC server fine.
2) Outlook via Crossover is slower than Outlook via Windows XP at getting initial updates on my laptop (dual-core 1.8Ghz Intel w/ 3GB RAM). once it's connected and downloaded though, it's just as fast. You can test if you're "connected" or not by just entering the wrong password - a bad password when you're connected gives you the password prompt again right away, but if it can't find the server for real, then it sits waiting for a long time.
3) There are some issues in the support ticket system (and the forums) about https certificates being odd. I fixed this by importing the HTTPS certificate into Firefox first, then setting up Outlook over HTTPS.
4) I couldn't get Outlook to work at all if I installed IE6, but the certificate posters said they needed to install IE6 to import the certs. I don't know which way is right.
So, check a few things surrounding those points, and if it's still not working, let us know what you mean by 'not connected' - IE: it comes up and says you're "offline" or says it's trying to connect continuously, or something else?