I have found out what the problem was.
We were generating the app that recieves the notifications directly from Xcode. The provisioning profile that was used for the app only worked for my collegue, but not for my own device. Since I was testing it the second time from the cloud, I presumed that the difference layed in the environment.
My advice is that when busy with the notification logic and it does not work is to start from fresh with the whole certificate process of apple.