I figured out that I needed vbrun6 but after I got past the key part, I got a wine crash.
[07/18/14 16:26:05] - Running wine-1.7.22 Steam.exe (Working directory : /home/steve7233/.PlayOnLinux/wineprefix/AOEIII_Complete/drive_c/Program Files/Steam)
[0718/162607:ERROR:resource_bundle.cc(417)] Failed to load C:\Program Files\Steam\bin\chrome.pak
Some features may not be available.
[0718/162607:ERROR:network_change_notifier_win.cc(126)] WSALookupServiceBegin failed with: 8
wine: Unhandled page fault on read access to 0x00000fc8 at address 0x7e669395 (thread 0047), starting debugger...
fixme:advapi:EventRegister {47a9201e-73b0-42ce-9821-7e134361bc6f}, 0x100211e0, 0x1009f068, 0x1009f060
fixme:advapi:EventRegister {58a9201e-73b0-42ce-9821-7e134361bc70}, 0x100211e0, 0x1009f0a0, 0x1009f098
fixme:advapi:EventRegister {3fa9201e-73b0-43fe-9821-7e145359bc6f}, 0x100211e0, 0x1009f030, 0x1009f028
fixme:advapi:EventRegister {1432afee-73b0-42ce-9821-7e134361b433}, 0x100211e0, 0x1009f0d8, 0x1009f0d0
fixme:advapi:EventRegister {4372afee-73b0-42ce-9821-7e134361b519}, 0x100211e0, 0x1009f110, 0x1009f108
fixme:imm:ImmGetOpenStatus (0x133ee0): semi-stub
fixme:ver:GetCurrentPackageId (0x33f15c (nil)): stub
fixme:imm:ImmReleaseContext ((nil), (nil)): stub
fixme:advapi:EventUnregister deadbeef: stub
fixme:advapi:EventUnregister deadbeef: stub
fixme:advapi:EventUnregister deadbeef: stub
fixme:advapi:EventUnregister deadbeef: stub
fixme:advapi:EventUnregister deadbeef: stub
(process:3615): GLib-CRITICAL **: g_slice_set_config: assertion 'sys_page_size == 0' failed
Any ideas?