Ok. I found a solution. I used:
export GOMP_CPU_AFFINITY=0-63
Instead of OMP_PROC_BIND. This is actually better in my opinion because, well, it works first of all, and secondly you can pick which threads get assigned to which cpus which is pretty cool.
Not sure why OMP_PROC_BIND didn't work, but it might be because I have a pre openmp 3.1 version installed. I'm using ubuntu 11.04 which has gcc 4.5.2. Tried to look up which openmp version comes installed with this gcc but couldn't find out within the first couple of minutes so I stopped searching. The method I used above works so I figured there's not much use in digging any deeper.