Rebuild form in AJAX callback
In your AJAX callback, use $form_state['rebuild'] = TRUE; (drupal_rebuild_form).

$form_state['rebuild'] is very useful in multistep forms, but it can also be handy in Ajax callbacks.

I recommend checking out the Examples project as well.  Both the Form examples and the AJAX examples.

If you will add the relevant snippets of your code I will try to add more details.