Sorry, just read your orrignal post and noticed you mentioned it there!
take a look at : http://bobblick.com/techref/projects/sv2pwm/sv2pwm.html
and: http://www.arduino.cc/en/Reference/PulseIn
and: http://www.arduino.cc/en/Tutorial/PWM
the way i'd go, would to be to measure the length of the high pulse and if its more than 1.5ms, set the direction pin, if not clear it.
then do some math to work out pwm ratio, so if pulse is 1ms then set pwm to 255, decreeaing to 0 when the pulse is 1.5ms and increading to 255 when the pulse it 2ms
hope this helps, but no promises that it will work, because i've not reli looked in to servos and rc control or experimented with it!