We've noticed that some people have problems when they do weird stuff to their phones. We use GCM for delivery, so that can stop working with a custom gapps install, or a rooted firewall setup, or disabled background data for gcm. We have yet to receive a report where GCM stops working for people with completely stock installs. If that doesn't describe you, please file a bug so that we can help get things working.

For what it's worth, TextSecure also has delivery receipts now, so the sender can see what's happening with their message.