Do you really need to use InnoDB? If so, you need to fine tune it order to get the best results, for example innodb_buffer_pool_size. In many cases, you should be fine with just MyISAM, though.
Have you tried disabling one plugin at a time?
Also, it may be your web host. If you can try your installation on another one, I would do that in order to rule that out.
Cheers!