Turning off oven breaker cuts power to AC, and vice versa. Why?
I misunderstood initially:  You have 2 breakers that both turn off the both devices.  This is consistent with two wires being swapped at the panel.

That is instead of 

Stove Red => Stove
Stove Black => Stove
AC Red => AC
AC Black => AC

You may have

Stove Red => Stove
Stove Black => AC
AC Red => AC
AC Black = Stove


Shut down power at the main breaker.
tag the 4 wires in question so you can put them back.  Call them AR, AB, SR, and SB for Air conditioner, Stove, red, black.
Turn the main breaker on
Turn the stove breaker on, the AC off.
Pull the stove from the wall and unplug the stove.
Measure the difference between the neutral and each of the hot wires.  If one is hot, and the other is not, then TPE's hypothesis is supported.


Fixing it.

If the above is the case, 


go back to  the panel, turn the main off, remove one wire from the stove's breaker, cap it, turn the power back on.
check the stove.  If the formerly hot wire is no longer hot, then the one you disconnected was the working wire.  
back to panel. Power off.  Reconnect working wire, disconnect other wire, cap it, power  on.
back to stove. Now the setup should be exactly the same as when you first did this.  (I can't think of a reason how it could be different, but I tend to make redundant checks.)


If the AC actually plugs in, you can test it the same way, just to verify that the problem is what you think it is.

When you make this set of tests, be sure the stove breaker is back off.  I think it should be that the same leg is the connected one.  That is, if SR was the connected on when you did the stove test with the AC breaker on, then AR will be the connected one with the Stove breaker off.

If this is the case, then swap the two unconnected wires.  If you use the example above, SB and AB swap.

At this point:


Turn stove breaker on, AC breaker off.
Go check stove outlet.  You should now have two hot legs. 
Check AC outlet.  You should have two dead legs.
Turn stove breaker off, AC breaker on.
Stove outlet should now be dead 
AC outlet should now have two hot lines.
Plug devices in. Turn both on.  
Verify that both work.


Note that all of this is based on the hypothesis that two legs of the breakers were reversed.  If, at some point, you get results that are incompatible with this hypotheses, it's time to stop, pour coffee, and rethink the whole process.

Note:  When I have done tests like this, I cap the loose wire if I'm going to turn the power back on.  This is probably paranoid, but I'm clumsy and easily distracted.  I don't really want to brush a hot wire because I got distracted.

As a sanity check (One mistake was made already...) Verify that neither devices has voltage floating around on exposed metal.  (I had a stove once that tried to kill me this way.)

I am NOT a professional Electrician.  This edit was an attempt to come up with a testing process for TPE's comment.