I don't think its necessarily an eCheck problem, and I'm pretty certain its not a "I upgraded to 1.3.7 and..." problem. Its a PayPal issue.
How do I know? well, I don't... but like many of you, I'm starting to have this problem sporatically in the last week or so. Unlike some of you (I presume) I upgraded to 1.3.7 the day it came out... and never had an issue until very recently.
Twice it was eChecks... so I thought that was the problem... but just this morning it happened again but with a normal PayPal payment.
A tip for Paperthreads and others worried about accounting/reports. Its simpler to fix than you think. Yes, you have to ask the customer what they ordered... but you don't need to ask them how much they paid or what taxes/shipping charges were there. Just find out what they ordered, then log in to your own store using their account (see Encrypted Master Password contrib) and place the order yourself. The taxes/shipping should be exactly what they saw. Instead of choosing PayPal, of course, choose some manual method (cheque/money order). Then go into the admin and change the order form Pending to Processing since you do have the payment.
Ok, its not ideal... but at least you don't have to ask them a million questions and, more importantly, the order is still on the books.
Hope that helps.