Arduino sensor ground isolation on motorcycle
You are correct in your assumption of how an optoisolator works.  

Yes I believe your issues can easily be caused by lack of isolation.  And direct connection to the bike's electrical will be "noisy" as opposed to a nice clean output from an optoisolator.  

Yes I believe that is the way to go.

I would do it for both sensors.

Your title question mentions ground isolation.  That may not be a problem, or it might be.  Best is if your Arduino's power suppply is regulated if running from the bike's battery.  I often use small 12v-to-5v converters (this is a search) to power my arduinos from noisy 12V sources like those types of batteries connected to trickle chargers.  Bottom line is that a noisy power source can mess up a perfect program.

I did some searching and came up with this optoisolator that does not require the grounds to be the same on both sides.  Optoisolator

It says long-distance, all that means is that the leads can be long enough for your purposes.  We do not give shopping or specific purchasing recommendations on this site, but I am showing this to you just to give you an idea of the kind of unit you should look for.  

If you can keep the grounds separate then by all means do so.  No good reason to get the bike's magneto impulses into your circuits.  Just running the wires will probably pick up some, so your optoisolator should be located next to the computer.  Let it clean up any extraneous signals that come in on the wires.

Sounds like a fun project.  Enjoy!