I think you are under billing for sure. I'm in Canada too (Calgary) and had the same problem. I also know the issue about "I haven't done it before and have no results or happy customers so how can I actually charge anything" mentality.
I had an advantage in that I was previously consulting and had decided to charge no less than $60 per hour or part of an hour. That can sound like a lot when you are an hourly employee, but remember there can be a lot of down time when you are starting out on your own. I also worked for large corporations as part of a negotiation team and have successfully negotiated several multi-million dollar contracts, so I know in my heart people are willing to pay if you ask them right and offer something of equal value. The key is, what is SEO worth?
Figure (and these are minimum amounts for someone with a lot of practice) 1 hour of Keyword research, 2 hours to optimise a handful of pages, 1 hour to submit the site (with custom descriptions), and at least 2 hours to follow up with logs and fixes. That's 6 hours, and believe me, I rounded down. $360 minimum. Or start getting used to being a not-for-profit company
Then I talked to some friends in this area (not SEO, Calgary business community) and discussed the rates. When they thought it was for website design they actually thought it was average, but when I explained the difference between design and SEO they all agreed it was too low. So I bumped it up to $500.
Then I contacted my first (paying) customer - a large liquor store owner - through my friend Rob. Rob's a great advantage for me because he's got a lot of marketing knowledge, runs his own business, and although he's scared to "break" something by messing with the settings, uses computers all the time for surfing, word, etc. Just like most potential small business clients.
At that point 2 things happened. First, Rob was positive I could get more money out of this client (after all, they were paying thousands per month on flyers) and I stopped by Google and read their recommendations for SEO's. At the time, they were recommending Money Back Guarantees (they don't anymore, for various reasons, basically because it's none of their business).
One problem with money back is the possibility that the client will allow you to optimize the site then demand their money back after the results are in, or make unreasonable demands. I came up with a way around this concern (I'm a lawyer so I have a bit of an advantage here) and then said its $500 per month for 3 months.
They said "WHAT!", and I said "I offer a 100% moneyback guarantee" and showed them the rules for it (Don't offer it without rules, IMHO) and pointed out what traditional advertising costs. They said OK.
They paid (in advance) and have since referred others. The bottom line is, don't be shy. It's a lot easier to come down in price than to raise them later. Second, get feedback from others - as you gain confidence and skills your ability to ask for money increases too.
SEO is worth more than website design for all but the most complex sites. If someone says "but my site only cost me x, why are you charging more?" you can point out that just because you can buy a telephone for $14.95 doesn't mean the phone company won't charge you more than that PER MONTH for a business plan. It's not the object, it's how it's used. A popular but plain site is worth more than a pretty but invisible one. It's 2 different things.
Hope that helps,
Ian