I recently found out that the latest version supports PulseAudio natively! You can download it from here. Currently, they are at version 126.96.36.199.
Previously, I had downloaded from the Medibuntu repository, which you can see here. But, they only offer version 188.8.131.52.
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.