Yes, I think there is a market for it. While I find that many people on this site are very computer literate, I am not and many people are not. In fact, the biggest problem (and problem is really too strong a word, but I'll use it for lack of better at this time) with this site is that so many people assume that everyone knows all about computers and technology. They'll refer to things that many people, especially myself, don't understand. I find myself reading and thinking "What in the world are they talking about? I don't have any idea what an RSS feed is".
I realize you're not talking about doing things regarding what this site does, but my point is that many people are not computer literate, especially people who are in their mid-40's and older. My wife often talks about wishing she knew more than just the basics. In fact, she often says she wished knew the basics about many things that are common to other people.
With proper marketing and sales help I think you could do quite well with it. Your idea of working on the phone with people is great. It's not like buying a DVD or book. It gives interaction so there can be questions from people and they can focus on areas that are important or difficult for them.
That's my two cents. Hope that helps.
I know that there's likely an abundance of training available on the net re: the applications you mentioned. However, I still believe you can't beat good old-fashioned "1:1" training even if it's virtual and recorded. Have you considered recording for product purposes, but then also offering weekly live interactive calls where your customers can join you online for Q & A? The way they would qualify to participate is by purchasing your product.
I for one would like some handholding on basic Photoshop!