I have two internet connections coming into my LAN. Due to logistical and geographical constraints, these internet connections come in to two separate routers. Each router serves its own LAN, but the two routers are connected to one another as well. My intention is to accomplish internet load balancing and fail-over between the two LAN's being served by these routers. Each router runs Zentyal 3.0.13 on Ubuntu 12.04.1 LTS. As a picture is worth a thousand words, I have attached a link to google drive where I have diagrammed my current setup: https://docs.google.com/drawings/d/1...it?usp=sharing

Once I get this all running, networking appears functional, but when I attempt to make a connection on the internet, it fails about 1/2 the time. To diagnose this, I run a ping from router1 on several websites which, sometimes fail with the following message:
From 192.168.42.101: icmp_seq=3 Redirect Host(New nexthop: 192.168.42.102)

And conversely, ping from router2 to a website will fail in the same way:
From 192.168.42.102: icmp_seq=3 Redirect Host(New nexthop: bradock.disith.prestergci.net (192.168.42.101))
note: bradock.disith.prestergci.net is the gateway address of router2.

We attempted to fix this by disabling ICMP redirects on both routers via the /etc/sysctl file, however, we still got the same ICMP redirect message anyway. Any idea how to address this issue?

You have two gateways with different public IPs, each doing NAT on all outbound traffic. In a non-NAT setup that would work, but in your case, router 1 doesn't know anything about entries in router 2's NAT table and vice versa. A setup like this wouldn't normally be able to do load balancing across internal subnets, although a not-completely-graceful failover (for outbound traffic) should be possible.

How did you configure routing and load balancing on these gateways? I would not expect one gateway to issue redirects pointing to the other gateway in a setup like yours, as the direct path should always have a lower metric than the path via the alternate gateway.

Let me say that I don't know the first thing about Zentyal. According to the Wikipedia article on Zentyal, it supports "multi-gateway rules, load balancing and automatic failover". If you've enabled those features, a configuration issue may very well be responsible for the redirects, and it may indeed be possible to achieve both load balancing and fault tolerance in a NAT scenario like yours. (A quick look at the documentation on the Zentyal web site didn't yield any obvious clues, though.)

The first test I'd do is disable balancing and try the pings. I'd restart the routers to be certain the balancing rules have been flushed.