Thanks @Roboe, I think this was indeed the problem. Also moxie mentions that a “bad gapps install” can cause the problem. Whatever that means exactly:
@oaim She’s not receiving GCM messages. That means either: 1. she has
background data disabled for TS or for Google services, 2. she has a bad
gapps install, 3. she has used something like titanium backup or
another backup/restore app, or 4. she’s on a network that blocks GCM.
So I think the solution is actually to reinstall Signal or in my case there was actually a Signal update in the PlayStore, which should be equivalent to reinstalling. This fixed the problem for me. What I didn’t like about reinstalling it, is that you can only backup your messages, but not your key, so everyone has to verify you again.
@freibadschwimmer: Seems like not many people in the community agree with forbidding LibreSignal. I actually can, since it’s the only way to ensure a verified build of Signal via the PlayStore. Otherwise there could be builds of LibreSignal or any other non-official implementation that contain ANY additional code, which would harm the trust in Signal. Also there is not really a metadata leakage by using GCM, since Google only gets to know the times you are communicating with anyone, but not whom. Although, I can of course understand the goal to get independent of Google.