It's about setting your expectations correctly and understanding the good ol' adage, "You get what you pay for."
First, the expectations need to be set. We live in an instantaneous world where we get just about everything we want the second we want it. Want to check your email? Now you've got an iPad, iPhone, and your computer letting you know the latest emails. Want to run a PPC campaign? You can get setup and running in minutes.
Throw all of that out the window with SEO. It isn't instantaneous and takes time to build your trust with the search engines. If it didn't you'd see a much more convoluted Google, one that people really would hate and not trust.
Again....
Give your SEO campaign time AND don't cheap out when purchasing services
IF you build a solid foundation of links and let those links age a bit, while creating some kick ass content for your niche, you'll dominate the search engines.
But, if you think throwing some junk spun content, mashed together with poorly designed link wheels and Fiverr gigs will get you to the top, then think again.