Changing Project Workflow

Hi,
I'm trying to change Project's workflow.

Old Situation : Projects with type "Fixed Price" and "Default" Workflow.
New Situation :
- A new Project Type "Mes Projets" asigned to a new Workflow "Gestion de Projet"
- New Workflow with new status (and also the old ones in order to change old Status to new ones)
- All status in new Workflow are linked to all other status (in order, during migration, to change Status in all ways)

Updating an existing Project with my new project Type "Gestion de projet"
=> unable to change from status "in progess" to any of my new status
=> unable to save Project because "le workflow ne vous autorise pas à passer cet élément dans cet état". I'm stuck on status "recorded" and no other status exist in combobox.

My question : what are the steps to "move" a project from one type to another, including workflow modifications ?

Thank you "en avance"

Thank you for your answer and sorry for lack of elements. I Thought I was just missing a step in my work.

I'm working with admin profile. All "Authorisation to change from one status to another" have the Administrator right checked.
Is your new type of project an operational type? I don't know what is "operational type"
What do you mean by "All status in new Workflow are linked to all other status"? => All new status created (inserted in a copy "Simple" Workflow) have hability to change from prior old status or next old status. For example, when i create 'Integration" between "in progress" and "done", the new status is able to change to "in progress" or "done". 
I'll try to make some screenshots to illustrate this in a few hours.