A couple of things on this one.
You don't need a trigger to change a record type.
A workflow + field update of the recordtype should just work fine.
I tested your exact scenario and this should just work.
A couple of things you should want to check:
- check that your record type is available to your users
- if you are testing this as an admin, remember that fields marked as read only on the page layout, you are still able to edit those as an admin
- try by adding the lead record type field to your page layouts to be 100% sure of the current record type of your record
If that still doesn't work, I suggest that you post a screenshot of your workflow rule + your workflow action(s).