OpenVPN TLS handshake failing – what ELSE could it be

I've got two very different clients on two very different networks, both unable to connect to a newly configured OpenVPN server, both causing log entries on the server like the following:

Aug  8 20:37:15 myserver ovpn-server[3797]: 12.34.56.78:48573 TLS: Initial packet from [AF_INET]12.34.56.78:48573, sid=80063aef 9e45c93a
Aug  8 20:38:15 myserver ovpn-server[3797]: 12.34.56.78:48573 TLS Error: TLS key negotiation failed to occur within 60 seconds (check your network connectivity)
Aug  8 20:38:15 myserver ovpn-server[3797]: 12.34.56.78:48573 TLS Error: TLS handshake failed
Aug  8 20:38:15 myserver ovpn-server[3797]: 12.34.56.78:48573 SIGUSR1[soft,tls-error] received, client-instance restarting

The clients are OpenVPN on a *buntu laptop computer connected to a NAT ADSL router, and a 3G/4G WWAN router with a built in OpenVPN client.

Here's what I've checked so far:

• Firewall is open (well duh, how else would TLS handshake even begin)
• Time/date is correctly set on both ends
• OpenVPN client is up to date (on the laptop at least, harder to check on the 3G/4G router)
• UDP port numbers do not change for the lifetime of the negotiation (see
  log above)

What ELSE could be causing this?

Edit: So, the plot thickens… In desperation I tried changing the whole chain of configs over to use TCP instead, otherwise leaving everything as it was. Bang! The OpenVPN client on my *buntu laptop was able to connect straight away. But what to do when the 3G/4G router's OpenVPN client doesn't even support TCP transport? I'm not done here yet!

Edit: Just to be clear here; I changed precisely four things to get this to work:

1. Edited OpenVPN's config to say proto tcp instead of proto udp and restarted OpenVPN
2. Added a new rule to the server's iptables firewall, to allow TCP 1194 – otherwise identical to the already existing rule allowing UDP 1194
3. Edited the protocol on the service definition on the firewall rule in the router my laptop is connected to allow TCP 1194 outbound instead of UDP 1194 outbound (just a drop-down box really)
4. Edited the OpenVPN connection information on my laptop via Network Manager and checked the Use a TCP connection checkbox

Every other setting and configuration remains identical to how it was before.

Edit: I have a sneaky suspicion that something odd is happening with the routing of the UDP traffic on my VPN server; the IP address that OpenVPN is configured to bind to is not the primary IP address of the server, in fact it's not even on the same subnet. Here's what the routing table looks like:

$ route
Kernel IP routing table
Destination     Gateway          Genmask         Flags Metric Ref    Use Iface
default         11-22-33-1.thing 0.0.0.0         UG    0      0        0 eth0
22.33.44.0      *                255.255.255.0   U     0      0        0 eth0
10.8.0.0        *                255.255.255.0   U     0      0        0 tun0
11.22.33.0      *                255.255.255.0   U     0      0        0 eth0

$ ip route
default via 11.22.33.1 dev eth0 onlink 
22.33.44.0/24 dev eth0  proto kernel  scope link  src 22.33.44.55 
10.8.0.0/24 dev tun0  proto kernel  scope link  src 10.8.0.1 
11.22.33.0/24 dev eth0  proto kernel  scope link  src 11.22.33.44 

The 22.33.44.55 IP address was assigned later, and is the one that OpenVPN binds to. Now I'm the first to admit that I know next to nothing about IP routing, but could it be that UDP traffic on the "new" IP address somehow gets lost due to it not having its own default route – or something?