Some people report Paltalk working with linux. However, setting up wine for the first time is a bit complicated.
You do not need a Windows installation to use Wine. However, if you do, Wine can use some files off it.
This is the deal: Wine has its own version of some Windows files, which you can tell it to use. You can also use the versions of your Windows installations, or look the files up on the internet. Most people report problems using Windows 2000 or XP's DLL files. Most people report success with Windows 98's DLL's.
I personally use Wine only for Kazaa. After setting it up, I had to download some Windows 98's DLLs of the net, and eventually got it to work with the latest version.
This person reports success running Paltalk with Wine. However, keep in mind that Wine is a complex application and most people need to tweak it and spend hours of work with the settings to get it to work.
I'd say that, if you plan on running Paltal tonight under Wine, give yourself ample time to install both Wine and Paltalk, configure Wine and troubleshoot weird problems.