For those like me who got an error while starting the game with the bottle shortcut (Wine serious error, the game does not even make it to the splash screen), it seems to be related somehow to the Launcher.exe file in the Borderlands Binaries folder.
Turns out that if you start the game with the other .exe file (BorderlandsGOTY.exe I think) in the same folder, it starts just fine. Hope this helps.