After upgrading to Ubuntu 11.10 I have found that my "open with gedit" right click menu in the file manager does not work unless I use it twice. Does anyone know why this might be?
Yep! This is a bug. I've reported it quite a while ago.
https://bugs.launchpad.net/ubuntu/+source/gedit/+bug/827414 is the bug report. At the end of September they showed a fix committed, but it's still acting the same way for me. I need to test a little more and respond to the thread.
Check which versions of of unity, unity-lens-files, and unity-lens-applications you have installed. They should be newer than 4.20.0, 0.6.10, and 0.4.12, respectively.