Spotify is probably one of the best cross platform apps I've seen, hands down.Are you using Spotify? Skype? VLC? Maybe Quassel? Go checkout some screenshots if not. Take a look. They are all written in Qt.
Who has said that using something like Qt or wxWidgets can't provide a native experience? This is a good comparison of what Qt looks like on different platforms, out-of-the-box. Qt has it's own renderer for most of the themes (some are native), wxWidgets completely uses the different native toolkits.
As far as Skype, they're not even remotely the same app on Mac/Windows.