To run phpmyadmin without getting 404 error, configure apache.conf for phpmyadmin.
gksu gedit /etc/apache2/apache2.conf
Then add the following line to the end of the file.
Include /etc/phpmyadmin/apache.conf
And restart apache
/etc/init.d/apache2 restart
Please read this section in Ubuntu wiki describes the 404 error problem for phpmyadmin.