Can I power A/C and furanance from two different services?
Usually, air conditioning units are simple things.  They have 


a freon hose in and out
240V electric power which runs the compressor 
a 24V signal wire which operates a big contactor that turns e A/C unit on.  


In this case, the furnace and the A/C unit are connected only by the freon hoses and the 24V thermostat line.  There is no mains AC power connection.  The furnace does not care where the A/C unit gets its power, it could come off a diesel engine and it wouldn't care.  

The 24V control power is generated by the furnace using a transformer, from its mains power supply.  However the 24V is its own totally separate service; it doesn't care which service the A/C unit is on. 

So... I think your problem is somewhere else.  I think that electricity isn't getting to the A/C unit, you didn't turn a breaker on, you disconnected the thermostat wire, etc. 

Or not...

If your air conditioning unit is not like I describe here, then that may be a problem.  There are some modern units that do some more complicated things. Fine then, so what? The fact is, a furnace unit draws fairly little electricity - only a few hundred watts for the fan to blow air around.  So the furnace adds fairly little load to the panel and it doesn't really need to be on a separate service in your case. 

Oh wait, your heat is electric? (Or heat pump with aux heat). Yes, electric heat is a very big load indeed. But like the air conditioner is supposed to be, the huge heating elements are contactor controlled, and are electrically very simple, and could be powered from a different service.