P2P connections are not always possible because of the different kinds of NATs and firewalls out there. please see this posting for more information about the kinds of problems different kinds of NATs cause:
in your case, where it seems like another application that's using Cirrus and RTMFP is working but yours isn't: you could have some kind of error in your application. does communication work reliably if you use VideoPhoneLabs, the Cirrus sample application?
if VideoPhoneLabs works but your application doesn't, then you probably have some kind of bug in your app.
the first link i posted explained about how different kinds of NATs can interfere with P2P communication. what does cc.rtmfp.net report at each end (your end and the other user's end)?
perhaps omegle detects when P2P won't work and uses a client-server relay for those cases.
NetConnection.AddressChange.Notify means that the server sees that the IP address and/or UDP port number you're using has changed. that can happen if your NAT has a very short translation timeout period, or if the NAT restarts or something, or if you change networks (perhaps going from wireless to wired for example).