You've gotten solid advice from your advisor. At the math departments at many research universities, it is very rare to seriously consider an applicant straight out of a PhD. However at most teaching jobs this is not rare at all.
These are rules of thumb, not absolutes. Eleven years ago in my department (UGA) we hired someone straight of a PhD program. This was a joint hire with engineering. Sixteen years ago we seem to have done something like this: we hired someone to be an NSF postdoctoral research fellow and an assistant professor. Nevertheless I think the chance that we would hire someone straight out of graduate school in 2015/2016 is essentially zero, and when someone decent applies only for an assistant professor position who is still a PhD student, I sometimes write to them to tell them that they should apply for a postdoc instead.
The number of postdoctoral jobs is safely smaller than the number of tenure track jobs at research universities, so we can conclude that some research universities are hiring tenure track faculty straight out of their PhD. For top 50 departments, this is very rare, but not impossible. On the other hand, you should feel free to apply to any university without a PhD program straight out of a PhD.
If you are not sure whether you are too junior to be seriously considered, what should you do? You should apply anyway. I've been on the "seeing hundreds of applications" side of it, and yes it is slightly annoying to see an application from someone who is too junior to be seriously considered. But that's ten seconds of annoyance, and it carries no lasting stigma against the applicant. In fact, often my reaction when reading the application is "Definitely not this year, but..."
I will risk a personal anecdote. When I was a graduating student, I was so naive about things that I assumed that even departments that didn't advertise postdocs nevertheless had postdocs to offer. (Oops.) In one case I got a reply, from a professor at an Ivy League school thanking me for my application for a tenure track job but telling me that they would go for someone more senior. (I will not name names, but suffice it to say that he wrote the book on elliptic curves, then wrote its sequel, and has written several other seminal texts in the years since.) He was remarkably gracious. About ten years later he visited my department, and during a group lunch I told this story. His response: "You never know who the young student will turn out to be in the years to come. So you might as well be nice." (Which was really a nice thing to say!) Anyway, clearly I had burned no bridges with my silly application. You shouldn't worry too much about this.
I also wonder why this state of affairs exists. If hiring committees are in fact burdened with such a quantity of under-qualified applications, why don't they filter some by clearly delineating what they are looking for in the job listing?
Job postings are heavily scrutinized for EEOC issues. If what you wrote last year got approved and worked decently enough, it is easiest not to mess with it. Here is a line from this year's job posting in my department:
A Ph.D., or equivalent foreign degree, in Mathematics or a closely related field is required.
I have asked in the past what a "closely related field" means and been told "Maybe nothing; we'll know it when we see it." I think I was involved in adding the "equivalent foreign degree" part: I believe that in Russia the degree is not called a PhD...The idea here is that if you list something as a requirement and then hire someone that doesn't meet the requirement, all hell could break loose. So even if we think that the chance that we'll hire someone without post-PhD training is 0.01%, that's still probably enough not to make that training a requirement.
Added: David Z points out that the possibility of taking multiple postdocs shows that the "we can conclude" above is not a watertight proof. I think a more protracted analysis of the number of tenure track jobs versus the number of postdocs and the number of postdocs one can take and still be competitive for a tenure track job would lead to the same conclusion.