Ah, but that brings up the obvious mirror argument... My time is so valuable that I find it economically advantageous to pay for SEO!
I'm not talking about doing the SEO for them. I'm more of about guiding the user to good SEO. Tell them what they should do, what keywords etc. How much would you pay for it? $49.95 ??
You can charge pretty much any price you want. Personally, I would just figure out how much I think my time is worth. I build my own sites and do my own SEO, but how I figure out if building a certain site was worth my time or not is by taking what profit I'm making and dividing it by about how many hours I put in it. Will sales of $49.95 be worth your while? How long will your "consulting" take? It is true, in this forum you are asking the wrong crowd, but there are people who still pay to get their sites submitted to search engines because they think it will do something for them LOL. There are a lot of people out there making money off people who want to get customers on their site, but don't know how to. You can be one of the legit ones out there offering good priced consulting. If I didn't know what I know now and if I had the money, I would jump on $49.95, but again is it worth your time?
The SEO consulting industry is pretty well established. Figure out what your target market is - i.e. what level of advice/service you want to offer and perform a competitive analysis. Do you want 1000 customers at $29.95 or 3 customers at $10K? There are all kinds of sites out there that can profit from well pointed advice. You could even do something where you set a target increase in revenue and set your fee as a percentage of your achieved goals. I think the low end markets are saturated, and the high end markets are the neighborhood of those SEO's who are also good at marketing and have an established history. The mid-range market where you give solid advice to sites that are already beyond the basics is pretty stiff in that they are very reluctant to pay for advice they might already know and are also reluctant to implement tactics they have already decided against. I would pay between $100 and $1000 if there was a quality person to pay the money to, but in my experience there isn't anyone out there that has any good information that's not a widely discussed forum topic already. The other problem I have with "paid SEO" is that usually you are involving recurring costs and that is problematic in and of itself. It's a good idea that you have, but a tough sell unless you have a very specific market that you are after.