Hi Zeester,
I use PayPal as one of my payment methods and have not had any problems yet. Is this a live site or are you suing the sandbox? If everything is set up correctly in the backend, this could be either a plug-in conflict or a PayPal issue. I know PayPal is doing major maintenance on their system this month.
Have you checked out the WooCommerce documentation to see how it handles order status?
http://docs.woothemes.com/documentation/plugins/woocommerce/
What type of product is it? Virtual, downloadable, simple, variable, subscription? If it is a subscription, the default order status after payment is ‘processing’.
“Once an order has been paid, WooCommerce only sets the status of the order to completed if all the products purchased in the order are both digital and downloadable. If all the products in an order are not digital and downloadable, the order will be marked as processing. This is to help you manage shipping of physical items.”
One thing you might try doing is deactivating/reactivating WooCommerce. It’s a shot in the dark, but you never know.
Nathan