Ok, I don't know if it was me or just installing it again, but what I did may be of help to others, so...
I was using PlayOnLinux from the repositories, without
unstable enabled, so even though there was this message about 3.8.12 being available,
apt-get upgrade didn't bring it to the latest version. So I followed the instructions on this page:
http://www.ubuntuupdates.org/ppa/playonlinux?dist=natty
I'll just post here the important commands to install PlayOnLinux 3.8.12:
sudo wget http://deb.playonlinux.com/playonlinux_natty.list -O /etc/apt/sources.list.d/playonlinux.list
sudo apt-get update
sudo apt-get install playonlinux
Even after that, portal didn't work. So I
purged PlayOnLinux and installed it and Steam from scratch. After that I just installed Portal from Steam (never used the PlayOnLinux installer for Portal) and it worked!!!
I'm not sure what I did wrong and what I did right, but it worked for me.... so I thought I might as well share. :D
Edited by vrash