I recently found out that the latest version supports PulseAudio natively! You can download it from here. Currently, they are at version 18.104.22.168.
Previously, I had downloaded from the Medibuntu repository, which you can see here. But, they only offer version 22.214.171.124.
One thing I noticed is that they recommend version 0.9.15 or greater. You can check to see what version you have with this command:
So, here is a screenshot of the audio setup screen for this new version of Skype. Notice that PulseAudio is an option now.