I just ran into this as well. I assume it’s because Contributors don’t have publish_posts permission. So, I’m upgrading them to Author for the interim.
I also vote for the second solution that allows the selection of any status and saving, even though that doesn’t keep strict adherence to a workflow. That way, if an error is made in selecting a status, Contributors can back up (e.g., from Pending Review to Draft).