There are definite pros and cons to each db type. The 'bragging rights of sorts for the InnoDB is that it supports row locking, as opposed to the entire table lock of the MyIsam. What does that mean for you? If you have a table that is read very often and is changed very often and the SQL statement uses a 'lock' command, the InnoDB will be slightly faster. As it only has to lock the row that is being manipulated as opposed to the entire table.
Other than that there really isn't to many difference between the two. It comes down to great d/b planning, making sure your tables are index, and making sure they are optimized.
[EDIT 2009-11-11]
After thinking about the problem a little more, I'm wondering if the problem is actually in the code. Databases are, very rarely, the root of the problem. Run some test queries from the gui/cli see how long an average query your program does takes. If the number is greater than half a second (.05), there is some room for optimization. If it is less than half a second your database is perfectly fine.
Once you optimize check the query times again. They will probably be even smaller now. I am willing to bet that the error is in the code.