I'm thinking, maybe not. There is no key or magic bullet, it's a combination of things, but if I were forced to come up with a single word as the "key," it's going to be content, and lots of it.
Let's start at the beginning, from your title "client expectations." After reviewing the client's server environment, business directives, etc., in response to "SEO our site" was your first response "For what keywords and terms?" (Sounds like a yes by your description.)
Second question is their niche, we cannot discuss specifics here (so don't) but is their market one glutted with millions of results, or a niche market that can be targeted well?
At this point it's your responsibility to educate your client: they will have to look at the competing sites, and understand in order to come close to competing, they are going to have to take part of the work load by generating content, either themselves or sent through you, for publishing. In the first case, this means they would have to build up a **lot** of content, in the second it may not be as difficult. But to answer your second question, inbound links are important, but they are nowhere near as important as content, lots of it, relevant to the topic.
After this discussion, it is **you** that needs to set the ground rules for client expectations. If you've made promises you can't keep, that's one thing; if the client has not followed your advice, that is something else entirely. So to answer the overall question, if you have allowed them to move forward with unrealistic expectations, the answer to "what to do?" is really just live and learn, make sure you clearly specify this in future projects, and make sure it's documented via your contract, or at the very least, email communications so you have something to refer to.
So let's move on to why they are not ranking "page one" and what you **might** be able to do about it.
When building these pages, are those keywords and terms on the page, not stuffed, but in natural language? Good usage of the title tag element - no redundant terms, keywords in the title, all titles unique and **relevant** to the page? Clean, optimized code, exposing your content more readily to the SE's?
Been up for a year, are you or the client constantly adding new content with relevant keywords, using them in your URL's, titles, meta descriptions, file names, alt tags, etc.?
If the answer to any of these is "well . . . mostly . . . " . . . not good enough. You can fix a lot of this stuff by digging around on this site and gleaning precious nuggets from some of the masters here - I have. :-)
At this point this is the direction I would go.
Having done all of the above in setting up a relationship with this client, I would be able to say "If you recall, I told you when we started that [huge competition market] was a tough market to rank in, and so far you haven't followed my recommendations - adding more content over the year. I can help with that, but as for the actual content of your site pages, you know your business best and you would have to contribute unique content, or at least give me some ideas to work with. I have a few excellent writers I work with that can provide article content at a very reasonable cost. If you'd like to move forward with this, let's see what we can do."
The saving grace for you - and most developers - is that clients are ALSO looking for the "magic bullet." Many times you go over all this with them and they forget - or more likely, don't care. For most of them, their impression is they throw money at it (you) and it's "just supposed to work." You have to constantly remind them of not only the limitations of The Way Things Work, but also your own limitations, and the groundwork on which your agreement was set.
Never pass on a project because they are an annoyance or you "don't have the skills." Look at every "problem" as an opportunity to expand your skills, meet the challenge, and in the process become better at what you do. But there is a big difference between "I can do that" just to land the client and a comprehensive response outlining what you can and cannot do for a client. This is where all problems and solutions come from.