Edit:
Ok I think the problem here is the modal bit, as the iPhone really appears to not like you having 2 views set to modal, or even animating from one modal view to another.
Do they definitely have to be modal? How about adding them to the normal navigation stack?
You could add the message view to the stack first (non-animated) so that it's there when you pop back one.
Try this:
The order in which you add views to the stack affects the order that they will display in when you dismiss them.
This part adds the composeController to the stack and then animates the picker going on top. Use this code to display the picker controller (ie instead of modal dialog):
[self.navigationController pushViewController:composeController animated:NO];
[self.navigationController pushViewController:picker animated:YES];
Then, when you are done with the picker, you can "pop" the view back to the message composer:
[self.navigationController popViewControllerAnimated:YES];
You should now have no references to any modal dialogs remaining in your code. I believe this should work much better than modal, which really is for displaying one view above every other one, not for switching from view to view.
Hope that helps!