I've had this problem too, usually after riding in bad weather, and more often an issue changing down rather than changing up, though I've had your 'skipped gear' problem too. In my case, the issue has always been a lack of lubricant exacerbating a problem of lack of adjustment. Whenever I have the dodgy shift problem, I remove, wash, and re-lube the chain (if inside my 200km cleaning schedule), clean the sprockets, chainwheels, and front and rear derailluers, and reinstall the chain. I then adjust the front and rear derailluers according to the methods shown here
http://sheldonbrown.com/derailer-adjustment.html. So far, this has always resolved the problem. I'm not a bike mechanic, so if your LBS can't fix this, there should be any number of other slightly less local BS's that can. That 'I can't fix it because it's a FWD recumbent' attitude is just blatant stupidity. The drivetrain on any recumbent is just 'standard bike'...only the chain is a little longer. On our Cruzbikes, there isn't even the excuse of a longer chain. When mine wore out, I replaced it with a standard Shimano 8 speed chain.
Sorry if I got a little carried away in my criticism of your LBS who you may quite like, but I work in the customer service industry (car parts), so I value product knowledge, customer service, and most importantly, a willingness to be flexible and understanding in the interpretation of a customer's issues.
That feels better!
Cheers,
Trev.