I solved it when I remembered that 'WSALookupServiceBegin failed with: 8', refers to an internet problem. I realized that the Steam Overlay must be bugged. I went into the Steam application, selected Civ 5 with a right click, selected properties, general tab and deselected use the steam overlay. The game works now. Steam for Windows and Mac gets bugged a lot to the point that wine has problems. You'd think Valve would be more careful since they obviously know that a lot of their players use Linux/wine. They even ported Steam to Linux via Steam for Linux.