Turns out, the problem was that I was using the 64bit version of Python. I downloaded it months ago and just forgot about that little fact.
Now, MinGW can only compile and use 32 bit libraries, not mix in 64 bit. This is what led to boost-python not compiling correctly (it's a wonder it did compile at all) and thus having undefined references when linked against.
Downloading the 32bit version of Python and recompiling boost solved the problems.