Seems like the d3d8.dll needs to be compiled on the same computer running psobb or else wine starts searching for directories on the machine the dll's were made in.
I was able to build wine 1.8.3 on my main system by adding --without-x --without-freetype, but I'm still getting the same crash before ship select.
http://pastebin.com/MbE9yaXS