If you are using Skype on Linux and run into the error message "P2P connect failed" while trying to sign in, then your configuration file is very likely corrupt. The fix is to just delete the .Skype directory from your home directory and restart Skype. If you have anything worth saving inside this directory, you can simply rename it instead or alternatively, back it up elsewhere prior to deletion.
The version of Skype on my system is 126.96.36.199 and it was installed (and upgraded) from the Medibuntu repository. I'm pretty certain that the previous version was working fine.