I have a Debian machine that I have previously installed MySQL on. In an attempt to delete it, I stupidly deleted the directories/files /etc/mysql/, /etc/init.d/mysql, /usr/lib/mysql/, /var/lib/mysql/. I then later did sudo apt-get purge mysql-server mysql-server-5.0.

Now, when I try to install mysql-server, I get:

$ sudo apt-get install mysql-server   
Reading package lists... Done
Building dependency tree       
Reading state information... Done
The following extra packages will be installed:
  mysql-server-5.0
The following NEW packages will be installed:
  mysql-server mysql-server-5.0
0 upgraded, 2 newly installed, 0 to remove and 0 not upgraded.
Need to get 0B/27.4MB of archives.
After this operation, 86.6MB of additional disk space will be used.
Do you want to continue [Y/n]? y
WARNING: The following packages cannot be authenticated!
  mysql-server-5.0 mysql-server
Authentication warning overridden.
Preconfiguring packages ...
Can't exec "/tmp/mysql-server-5.0.config.122781": Permission denied at /usr/share/perl/5.10/IPC/Open3.pm line 168.
open2: exec of /tmp/mysql-server-5.0.config.122781 configure  failed at /usr/share/perl5/Debconf/ConfModule.pm line 59
mysql-server-5.0 failed to preconfigure, with exit status 255
Selecting previously deselected package mysql-server-5.0.
(Reading database ... 158138 files and directories currently installed.)
Unpacking mysql-server-5.0 (from .../mysql-server-5.0_5.0.51a-24+lenny5_amd64.deb) ...
Selecting previously deselected package mysql-server.
Unpacking mysql-server (from .../mysql-server_5.0.51a-24+lenny5_all.deb) ...
Processing triggers for man-db ...
Setting up mysql-server-5.0 (5.0.51a-24+lenny5) ...
Stopping MySQL database server: mysqld.
110206 19:31:13 [ERROR] /usr/sbin/mysqld: Can't find file: './mysql/user.frm' (errno: 13)
110206 19:31:13 [ERROR] /usr/sbin/mysqld: Can't find file: './mysql/user.frm' (errno: 13)
ERROR: 1017  Can't find file: './mysql/user.frm' (errno: 13)
110206 19:31:13 [ERROR] Aborting

110206 19:31:13 [Note] /usr/sbin/mysqld: Shutdown complete

/etc/init.d/mysql: WARNING: /etc/mysql/my.cnf cannot be read. See README.Debian.gz (warning).
Starting MySQL database server: mysqld . . . . . . . . . . . . . . failed!
invoke-rc.d: initscript mysql, action "start" failed.
dpkg: error processing mysql-server-5.0 (--configure):
 subprocess post-installation script returned error exit status 1
dpkg: dependency problems prevent configuration of mysql-server:
 mysql-server depends on mysql-server-5.0; however:
  Package mysql-server-5.0 is not configured yet.
dpkg: error processing mysql-server (--configure):
 dependency problems - leaving unconfigured
Errors were encountered while processing:
 mysql-server-5.0
 mysql-server
E: Sub-process /usr/bin/dpkg returned an error code (1)

I have tried to search for a solution via Google and have found lots of suggestions for this problem, but ultimately it seems like the problem is that by deleting the files manually, I messed up the mysql-common package.

I have tried to do

sudo apt-get install --reinstall mysql-common

followed by installing mysql-server, but it does the exact same thing.

I previously had MySQL working great, I just want to get it back to that state. Thanks so much for your help.