A new version of the Android Market is living in the wild as version 3.1.5 – you can download and install it below. Still not exactly sure what was included in the jump from .3 to .5, but we have all day now to figure that out.
Download: Market_3.1.5.apk [mirror]
Install as you would any other .apk file. Download and tap install.