You should have plenty of processing power to do everything you need. Initially make sure that you have no delay() or waiting timeouts in the code. This is usually the killer for most new programmers as even 1 millisecond repeated in a loop can cause a big delay. Eliminate these by implementing Finite State Machine techniques.
What else you can do depends on what your priorities are. If the LEDs are secondary priority to the IR then putting up with a slightly irregular pattern may be easiest.
Look at interrupt routines to receive and send the IR characters. I use an IR library (IRRemote) that does not cause me delays http://arcfn.com/2009/08/multi-protocol-infrared-remote-library.htm http://arcfn.com. If nothing else you may want to see how this person has implemented his code.