Following on from my discovery that the Visio option is only available on machines that have Visio installed i found another oddity.
I have two lists, one is just a regular "Tasks" and the other is a "Project Tasks".
In the Task list I am able to see the "create visio diagram" option (and it works) but in the Project Tasks the option is not there. Both lists allow me to export to Excel or open in Access.
Is there a property somewhere that will allow me to create Visio from a Project Task list?