My user base ranges from wiki-experts to computer novices. The novices are usually unable to grasp the idea of a markup language and give up before making contributions.
I don't understand this. I have people who can barely switch on their computer using the wiki happily. A lot of users find it hard to get started, so I often spend a bit of time getting them on to it, then add more capabilities (like Categories) later. Maybe they need a bit of coaching. You don't have to do it all - I have them training each other now.
maybe borrow our 'beginner's overview'? A lot of them have said it is very useful. http://tinyurl.com/7yhjy. It's for mediawiki not any other software.