This is a strange one
I tried pinging them, but they don't respond to pings so that doesn't help much (btw, website works fine from my CentOS box)
But an nmap probe of port 80 (with no pings) shows connectivity:
$ ping fishandgame.idaho.gov
PING fishandgame.idaho.gov (220.127.116.11) 56(84) bytes of data.
--- fishandgame.idaho.gov ping statistics ---
3 packets transmitted, 0 received, 100% packet loss, time 1998ms
$ nslookup fishandgame.idaho.gov
Don't really know what to suggest next. Maybe you can capture packets for a failed connection attempt in Wireshark and we can take a look to see if we can figure out where it's all going wrong from the packet capture.
# nmap -sS -p 80 -P0 fishandgame.idaho.gov
Starting Nmap 4.11 ( http://www.insecure.org/nmap/ ) at 2007-10-12 11:24 BST
Interesting ports on h66-83.state.id.us (18.104.22.168):
PORT STATE SERVICE
80/tcp open http
Nmap finished: 1 IP address (1 host up) scanned in 0.525 seconds