Just a note, if anyone is having the same problems and have similar information on the /etc/lsb-release file, changing the line "DISTRIB_RELEASE=7" to " DISTRIB_RELEASE=7.1" also seems to fix the problem.
I'd like to report that I did a clean install with 2 Debian Wheezy machines and installed Plesk on it without any issues. I cannot reproduce the issues mentioned here, but perhaps this was fixed before I installed those machines.