When you want to trigger a workflow based on a change of appointment status, simply use the appointment status trigger.

As you can see in the image, I chose to check the appointment status to see if it was "new".

Also, I set the Calendar as well. Without this the system will trigger the workflow anytime someone's appt status changes without regard to the calendar.

There are a lot of options in this trigger. If you think this is the right trigger to use for what you want to do, you are probably right and just need to choose the right options.