If you're troubleshooting EoIP connection issues, especially if they're really odd connect/non-connect issues, check your NAT settings.
I've spent far too much time on and off over the past 2-3 months trying to troubleshoot EoIP issues. It's a really nasty network I'm running over, with multiple VPN links, wired links, wireless links, 2 continents, and a bunch of Hotspot servers. I'd love to say I understood every aspect of what was going on in it, but... even though I did the initial setup, I'm not totally sure I understand every aspect.
I had two boxes, many hops apart, that could ping each other, could telnet/SSH to each other, and generally appeared to be perfectly happy talking. EoIP tunnels would mostly not function. Sometimes I'd get one halfway running, but they mostly weren't working. Unfortunately, sometimes, they'd work just enough to kick me into "Why is this erratic?" mode instead of "Why isn't it working at all?" mode.
After a bunch of investigation of links/hops/routing/etc, I traced the issue down to a NAT issue. There were routes to IP space, but some of the data was getting tagged by a NAT rule, and masqueraded. The boxes could talk, but packets from one box were being src-nat'd to a different IP, leading to the issues I was seeing.
I set up some new private IP ranges and made sure nothing was being NAT'd, and things started working properly.
Hopefully this helps someone out. I searched for quite a while and couldn't find anything, so it was a large bit of trial & error to find the issue.