When you loaded the clean install of v1.3.7 did you also load the current PayPal Patch?
http://www.zen-cart.com/forum/showthread.php?t=56216

Are you able to do a regular checkout with Check/Money order?