Check the Exim4 Logs to see what's the problem, there might be something missing on the Exim4 config:
sudo tail /var/log/exim4/mainlog

I get this error before the queue ends

R=dnslookup T=remote_smtp defer (111): Connection refused

I also realized that my install of exim gave this error at some point:

postmulti: fatal: config variable inet_interfaces: host not found: loopback-only
[ OK ]

Now I am getting these errors:

2014-03-04 17:32:46 socket bind() to port 25 for address 127.0.0.1 failed: Address already in use: waiting 30s before trying again (3 more tries)
2014-03-04 17:33:15 socket bind() to port 25 for address 127.0.0.1 failed: Address already in use: waiting 30s before trying again (5 more tries)
2014-03-04 17:33:16 socket bind() to port 25 for address 127.0.0.1 failed: Address already in use: waiting 30s before trying again (2 more tries)
2014-03-04 17:33:45 socket bind() to port 25 for address 127.0.0.1 failed: Address already in use: waiting 30s before trying again (4 more tries)
2014-03-04 17:33:46 socket bind() to port 25 for address 127.0.0.1 failed: Address already in use: waiting 30s before trying again (1 more try)
2014-03-04 17:34:15 socket bind() to port 25 for address 127.0.0.1 failed: Address already in use: waiting 30s before trying again (3 more tries)
2014-03-04 17:34:16 socket bind() to port 25 for address 127.0.0.1 failed: Address already in use: daemon abandoned
2014-03-04 17:34:45 socket bind() to port 25 for address 127.0.0.1 failed: Address already in use: waiting 30s before trying again (2 more tries)
2014-03-04 17:35:15 socket bind() to port 25 for address 127.0.0.1 failed: Address already in use: waiting 30s before trying again (1 more try)
2014-03-04 17:35:45 socket bind() to port 25 for address 127.0.0.1 failed: Address already in use: daemon abandoned

Check your firewall settings:
sudo iptables -L

If you have issues with the configuration try Exim's configuration tool:
sudo dpkg-reconfigure exim4-config

You can't run multiple MTA. You already have something listening on port 25.