Second question first (also turning on error reporting might help with the first problem) - headers usually don't work because something is being output to the browser before the headers. The easiest way to troubleshoot this (and most other errors that php can detect) is to turn on full php error_reporting and set display_error on. On a development system, this is best done in the php.ini or a .htaccess file so that fatal parse errors are output as well. Turning on full php error reporting will also help you when learning php or anytime your are developing php code or debugging php code.
I'll assume this is on your own computer. In your php.ini set the following two values (stop and start your web server to get any changes made to php.ini to take effect) -
I included the E_STRICT setting in the above so that you will also be notified if you are using any depreciated functions that could be turned off or removed in future versions of php.
For the first problem - your query is apparently executing without error (the or die() statement is not being executed), so, echo what the actual query string is and then check directly in the database using your favorite database management tool to make sure the values match.
I recommend forming your query string in a variable so that you can echo it and then using that variable in the mysql_query() statement. Doing this will also help you as you write more sophisticated programs because you can then echo the query when an error occurs or log all queries to keep a record of who did what to your database.