Changing BaudRate in both sides simultaneously
Send command to change baudrate from PC to microcontroller on the old baudrate.
Send ACK for the command on old baudrate from microcontroller to the PC. 
Change baudrate on PC and have the microcontroller execute the baudrate change. 
Wait x ms (to be sure both sides are done with the baudrate change). 
Send some data from microcontroller to PC on the new baudrate to check baudrate change is succesfull.
PC doesn't receive data within x+y ms, go back to old baudrate.
If the microcontroller doesn't get an ACK to the data from step 5 within z ms change back to old baudrate


Waiting times x, y and z will be need to be determined based on how fast both sides can switch baudrate and any possible delay caused by the whole chain (Program, OS, hardware). Here i would say it's better to wait a bit too long than too short, unless there is some reason you need to change quickly.

Step 5 to 7 are there to ensure you'll be pretty sure it will be possible to communicate after x + y + z ms, be it on the new baudrate or the old one.

Also from code you post i understand the ACK message is a single "*"? If so it might be an good idea to expand the ACK message so that the other side knows what message is getting acknowledged. 

edit:

In the code for you microcontroller you put the * in the send buffer and directly after that you start fiddling with the baudrate registers. Meaning you're changing the baudrate while its sending the ACK.
The easiest solution is to have the microcontroller wait untill it's done sending the ACK with a:
while(UCA1STAT1 &amp; 0x01);. 
UCA1STAT is the status register of the UART (Userguide for the MSP430 family page 914). And bit 0 will be 1 if the UART is busy sending or receiving. 

A word of warning for the solution above, if for some reason the UART busy bit stays high the microcontroller will hang. Plus the microcontroller can't do anything else in the meantime. The term for this is blocking code/function.