Hi offie,
Your problem may be due to a sessions problems, which you have to check your configure.php in catalog/.. and admin/.. directories along with your sessions options, as you were told in another forum.
If the problem is not solved, there is an error that you have to chase, for that..
Try this:
1. Check you are using a "business" account with Paypal and try again. Otherwise continue to point 2.
2. Try creating a Sanbox account, and then inside create a "fake" personal account.
3. Then, create a "fake" business account.
4. With this "fake" business account create new API credentials.
5. Set this new business account and its credentials in your admin/modules/payment chekout express settings.
With this you can test Paypal express many times without affecting your credit card and you will get error messages that
can give you a clue.
Let's see where it leads you.
Hope this help..