First you need to generate an md5 hash of the password you want to use. You can use an online generator like the one at http://www.adamek.biz/md5-generator.php
md5("password1234") = "bdc87b9c894da5168059e00ebffb9077"
Please don't use the one above but you will be using the long string on the right between the quotes.
Go to your phpmyadmin and open the wp_users table and click on insert and put in your login, email nicename along with the md5 password hash you created. You should also put 1 for the user id since it was probably your previous admin user id.
Next go to the wp_usermeta table and add an entry using wp_capabilities as the meta_key, 1 as the user_id and leave the umeta_id blank. for the meta_value paste this in.
Next add another entry in the same table using wp_user_level as the meta_key, 10 as the meta_value and 1 again as the user_id.
Clear your browser cache and log back in to your dashboard. When you do this WordPress will update the md5 hash you added to the db as a proper salted and encrypted password. ( you still use the same password on the front end ).