Which first: upgrade mysql version or convert storage engine?
Of the choices, I would update, then convert.

InnoDB received some massive performance boosts in 5.5, so by upgrading first you get some features that 5.5 introduces, and then you can convert to InnoDB to get full innodb benefit. 

5.0 InnoDB performance was not great, so you might see some strange issues by converting to InnoDB prior to updating to 5.5

As always though, read through the MySQL 5.5 upgrade notes to make sure there's nothing new that would break your current implementation.

And, of course, test it out on a non-production database first.