Those who, after a seemingly successful upgrade from Magento 1.3.x to Magento 1.4.0.1, have problems with Magento acknowledging PayPal payments (changing order status from Pending Payment to Processing) and sending out New Order emails to their clients should do/check the following things:

In PayPal: Go to My Account -> Profiles -> More Options -> Instant Payment [...]