W: Failed to fetch http://security.ubuntu.com/ubuntu/dists/lucid-security/Release.gpg Something wicked happened resolving 'security.ubuntu.com:http' (-5 - No address associated with hostname)

Fix'd thanks to: this post.

I had the same error on a new install. It looked like a DNS issue. So I configured my network connection to use OpenDNS directly, rather than via my router. That seems to have solved the problem.

Right-click network icon, select "edit connections"
Select the connection you are using at the moment.
Click "edit"
Select the "IPv4 settings" tab
Set method to "Automatic (DHCP) addresses only"
Then input "208.67.222.222, 208.67.220.220" into the DNS servers box

Exit, reset the network connection and retry "apt-get update"

Weird that my ISPs DNS doesn't resolve some of the addresses now :/