I was able to find the culprit, and it was related to caching the pixel link. I appended a random string to the img src and it works in both ymail and gmail now.
The image tag now looks something like this:
<img src="http://mysite.com/email_track.php?email=email_value&country=country_value&state=state_value&random_value=<?php echo rand() ?>" />
Thanks for the help in guiding me towards this discovery.