Ubuntu+Apache2 – Not allowing outside connection

I've got a box running Ubuntu 10.04, and I have Apache2 installed. When I'm on the box I can go to http://localhost/ and it connects to the web server fine. I can also go directly to my IP and connect no problem. However, if I try to connect from another computer on the network, either through the DNS or direct IP, my connection times out.

However, I can connect to the box via SSH just fine, as well as ping the box.

Any ideas?

Thanks

UPDATE:

When running nmap on the local computer I get the following:

wayne@media-box:~$ sudo nmap -sS -O -PI -PT 192.168.1.70

Starting Nmap 5.00 ( http://nmap.org ) at 2010-06-28 06:32 CDT
Interesting ports on media-box (192.168.1.70):
Not shown: 995 closed ports
PORT    STATE SERVICE
22/tcp  open  ssh
25/tcp  open  smtp
80/tcp  open  http
143/tcp open  imap
993/tcp open  imaps

However, if I run it from another box on the network:

Starting Nmap 5.00 ( http://nmap.org ) at 2010-06-28 06:32 CDT
Interesting ports on media-box (192.168.1.70):
Not shown: 998 filtered ports
PORT    STATE  SERVICE
22/tcp  open   ssh
113/tcp closed auth

So 80 is open to the box itself but not the outside world? How do I fix that?