Is this fresh install or was there already MySQL server running before?

First of all check if mysqld really didn't start, since the init.d script gives it only 14 seconds by default after it reports "failed" which is often not long enough.
And most important - read the mysql error log.

If mysqld is starting longer but successfully then just set the time longer to make the apt-get succeed:
edit /etc/init.d/mysql

for i in 1 2 3 4 5 6 7 8 9 10 11 12 13 14; do

to e.g.

for i in `seq 1 90`; do

BTW meant to mention this is a brand new fresh clean install of Debian 6 64bit (no previous mysql packages installed that I know about) also there is absolutely nothing in the mysql logs, which I thought was strange. However there is some stuff in the syslog, just not sure if it would help figure out what is wrong.

Mar 16 03:58:15 steven mysqld_safe[25395]: #007/usr/sbin/mysqld: Can't create/write to file '/tmp/ibVMew5n' (Errcode: 13)
Mar 16 03:58:15 steven mysqld_safe[25395]: 120316 7:58:15 InnoDB: Error: unable to create temporary file; errno: 13
Mar 16 03:58:15 steven mysqld_safe[25395]: 120316 7:58:15 [ERROR] Plugin 'InnoDB' init function returned error.
Mar 16 03:58:15 steven mysqld_safe[25395]: 120316 7:58:15 [ERROR] Plugin 'InnoDB' registration as a STORAGE ENGINE failed.
Mar 16 03:58:15 steven mysqld_safe[25395]: 120316 7:58:15 [ERROR] Unknown/unsupported storage engine: InnoDB
Mar 16 03:58:15 steven mysqld_safe[25395]: 120316 7:58:15 [ERROR] Aborting
Mar 16 03:58:15 steven mysqld_safe[25395]:
Mar 16 03:58:15 steven mysqld_safe[25395]: 120316 7:58:15 [Note] /usr/sbin/mysqld: Shutdown complete
Mar 16 03:58:15 steven mysqld_safe[25395]:
Mar 16 03:58:15 steven mysqld_safe[25399]: 120316 7:58:15 [Note] Flashcache bypass: disabled
Mar 16 03:58:15 steven mysqld_safe[25399]: 120316 7:58:15 [Note] Flashcache setup error is : ioctl failed
Mar 16 03:58:15 steven mysqld_safe[25399]:
Mar 16 03:58:15 steven mysqld_safe[25399]: 120316 7:58:15 [Note] Plugin 'FEDERATED' is disabled.
Mar 16 03:58:15 steven mysqld_safe[25399]: 120316 7:58:15 InnoDB: The InnoDB memory heap is disabled
Mar 16 03:58:15 steven mysqld_safe[25399]: 120316 7:58:15 InnoDB: Mutexes and rw_locks use GCC atomic builtins
Mar 16 03:58:15 steven mysqld_safe[25399]: 120316 7:58:15 InnoDB: Compressed tables use zlib 1.2.3
Mar 16 03:58:15 steven mysqld_safe[25399]: 120316 7:58:15 InnoDB: Using Linux native AIO
Mar 16 03:58:15 steven mysqld_safe[25399]: #007/usr/sbin/mysqld: Can't create/write to file '/tmp/ib7GzNTr' (Errcode: 13)
Mar 16 03:58:15 steven mysqld_safe[25399]: 120316 7:58:15 InnoDB: Error: unable to create temporary file; errno: 13
Mar 16 03:58:15 steven mysqld_safe[25399]: 120316 7:58:15 [ERROR] Plugin 'InnoDB' init function returned error.
Mar 16 03:58:15 steven mysqld_safe[25399]: 120316 7:58:15 [ERROR] Plugin 'InnoDB' registration as a STORAGE ENGINE failed.
Mar 16 03:58:15 steven mysqld_safe[25399]: 120316 7:58:15 [ERROR] Unknown/unsupported storage engine: InnoDB
Mar 16 03:58:15 steven mysqld_safe[25399]: 120316 7:58:15 [ERROR] Aborting
Mar 16 03:58:15 steven mysqld_safe[25399]:
Mar 16 03:58:15 steven mysqld_safe[25399]: 120316 7:58:15 [Note] /usr/sbin/mysqld: Shutdown complete
Mar 16 03:58:15 steven mysqld_safe[25399]:
Mar 16 03:59:46 steven /etc/init.d/mysql[26505]: 0 processes alive and '/usr/bin/mysqladmin --defaults-file=/etc/mysql/debian.cnf ping' resulted in
Mar 16 03:59:46 steven /etc/init.d/mysql[26505]: #007/usr/bin/mysqladmin: connect to server at 'localhost' failed
Mar 16 03:59:46 steven /etc/init.d/mysql[26505]: error: 'Can't connect to local MySQL server through socket '/var/run/mysqld/mysqld.sock' (2)'
Mar 16 03:59:46 steven /etc/init.d/mysql[26505]: Check that mysqld is running and that the socket: '/var/run/mysqld/mysqld.sock' exists!
Mar 16 03:59:46 steven /etc/init.d/mysql[26505]:

I tried to increase the time limit using this code however it had no effect. Thanks though anything else you might think could be causing this?

Ok, in this case increasing timeout won't help.
In debian by default mysql logs to syslog, but you can define separate error log file by setting in /etc/mysql/my.cnf e.g.
log_error=/var/lib/mysql/error
Any way the log says that something's wrong with your /tmp
Do you have free space on your disk? Are the permissions correct for /tmp?
What is your output of:
df -h
ls -ld /tmp

Output of df -h:
Filesystem Size Used Avail Use% Mounted on
/dev/sda2 1.9G 168M 1.7G 10% /
tmpfs 5.9G 0 5.9G 0% /lib/init/rw
udev 5.9G 176K 5.9G 1% /dev
tmpfs 5.9G 0 5.9G 0% /dev/shm
/dev/sda1 92M 23M 64M 27% /boot
/dev/sda8 191G 188M 181G 1% /home
/dev/sda6 9.2G 750M 8.0G 9% /usr
/dev/sda7 9.2G 456M 8.3G 6% /var

Output of ls -ld /tmp:
drwxr-xr-x 2 root root 4096 Mar 16 16:17 /tmp

Thanks so much for helping me. Hopefully I can figure out where the problem is today. I've been trying for a day now. I think it might be the way the hard drive was partitioned?

/tmp permissions are wrong, write ones are missing.
You may do

chmod 777 /tmpchmod +t /tmp

or you can set another directory for mysql temp storage, e.g.

mkdir /var/lib/mysql/tmpchown mysql.mysql /var/lib/mysql/tmp

then in my.cnf:
tmpdir = /var/lib/mysql/tmp