Multi-threaded Real-time Operating Systems (RTOS) are the common solution to this problem. Many RTOSes are available and I have ported two free open source systems to Ardruino.
FreeRTOS http://www.freertos.org/ is very popular and ChibiOS ChibiOS free embedded RTOS - ChibiOS Homepage has some nice technical features.
You can download Arduino versions of these systems here http://code.google.com/p/beta-lib/downloads/list as FreeRTOSBeta20121215.zip and ChibiOSBeta20121212.zip. Install them and run the examples.
Here is a nice paper on FreeRTOS http://stiff.univ-brest.fr/~boukhobza/images/stories/Documents/Teachings/OSM/expo/FreeRTOS_Melot.pdf.