http://bugs.winehq.org/show_bug.cgi?id=33478
--- Comment #15 from jack q@cyphernaut.org 2013-09-04 13:58:51 CDT --- This set of patches seems to have fixed my issues:
http://www.winehq.org/pipermail/wine-devel/2013-September/101106.html
This is 100% unscientific, but after applying those patches and disabling StrictDrawOrdering Borderlands2 runs flawlessly with fglrx.