I also had this problem and ended up installing oscommerces paypal IPN thinking in addition to its better features it might also solve this problem. It didnt. I did fix however by making sure the code for your currency in localized settings is exactly the same as that specified in the paypal module (in administration area). In my case for australian dollars i had AUS instead of AUD.
If you have the above correct you might want to check your paypal is setup for AUD and there is also a contribution for this but i have not tried it, http://www.oscommerce.com/community/contributions,2865