You have :
$sql2="SELECT * FROM navigation WHERE view_name='".$view."'";
but then only mention an index on "nav_id". Shouldn't there be an index on "view_name" or did you intend to type "view_name" and ended up typing "nav_id"?
Logging slow queries as well as logging joins for which there were no indexes to use are VERY powerful and I often use but there is one thing to remember, if the MySQL server is heavily loaded, queries that should take single digit miliseconds to complete can all of a sudden start taking seconds so it is good to take the data in the long query log with a grain of salt.
One thing that I have found is that the more joins there are in a given query, the more chances there are for a given table that the joins depends on will be locked at the time of the query, due to the record or table, depending on table type, being updated. In other words, start with the ugliest queries and either optimize or split them up as needed so they no longer show up in the long query log and you'll likely find that unrelated queries that showed up in the log previously are no longer there.
In the case of multi-table joins, although they are elegant and in most cases more efficient, they basically expose one to a greater chance of running into locked table conditions.
But, all that said, if the only change you made was OS rev. level and although optimizing MySQL whenever possible is good, it is even better to resist the urge to apply a band-aid to one's elbow because their knee is smashed and search out the root cause itself.
One last thing, it is also important to make sure that one isn't delving into the world of quantum physics where the outcome of an experiment changes simply by observing the experiment. I can't count the number of times I started searching for the root of a MySQL problem that I just discovered only to find that the "problem" had always been there, I just hadn't been in the right situation to observe it before.
That's not to say that there isn't a problem or that it is not happening but instead, make sure that you are observing an average of load times over the course of a few days to a week to make sure that you aren't just seeing things at their worst.
By the way, do you use MySQL Administrator? Using the real time stats and graphs really really helps get a better idea of what is going on. I've gotten to the point where I can tell you, within a couple of dozen visitors, how many totally visitors are active on a given site that normally has up to 20k visitors in a 30 minute period of time. That's not due to my expertise, that's due to MySQL Administrator making it so easy.
I apologize if nothing I've written is new to you as I'm no expert either but what I have learned, came at a GREAT cost and I'd like to share it to get more bang for my buck!