How do I remove the LAMP stack so I can start over?

sudo apt-get purge mysql-server apache2 php5

That will remove the "big-boy" packages, which should take care of most cases.

You can find this information in the documentation, specifically this section on how to start over:

To remove the LAMP stack remove the following packages:

Note: This assumes you have no other programs that require any of these packages. You might wish to simulate this removal first, and only remove the packages that don't cause removal of something desired.

sudo apt-get remove apache2 apache2-mpm-prefork apache2-utils apache2.2-common libapache2-mod-php5 libapr1 libaprutil1 libdbd-mysql-perl libdbi-perl libmysqlclient15off libnet-daemon-perl libplrpc-perl libpq5 mysql-client-5.0 mysql-common mysql-server mysql-server-5.0 php5-common php5-mysql

To also remove the debconf data, use the purge option when removing. To get rid of any configurations you may have made to apache, manually remove the /etc/apache2 directory once the packages have been removed.

Don't use tasksel to remove packages, bad things can happen, this is covered in this bug report.

The rest of the documentation covers how you would reinstall apache and all the stuff you'll need to get going again.

Remove LAMP

sudo apt-get purge libapache2-mod-auth-mysql phpmyadmin
sudo apt-get purge mysql-server mysql-server-5.1 mysql-server-core-5.1
sudo apt-get purge apache2 apache2-mpm-prefork apache2-utils apache2.2-bin apache2.2-common libapache2-mod-php5
sudo apt-get autoremove

Install LAMP

Run tasksel Select LAMP server.

To fully manage your lamp Server database, install phpmyadmin

sudo apt-get install phpmyadmin

sudo apt-get purge apache2 php5-cli apache2-mpm-prefork apache2-utils apache2.2-common \
     libapache2-mod-php5 libapr1 libaprutil1 libdbd-mysql-perl libdbi-perl \
     libnet-daemon-perl libplrpc-perl libpq5 mysql-client mysql-common mysql-server \
     php5-common php5-mysql phpmyadmin \
&& sudo apt-get autoremove