Versioning – When Should Version Number Be Incremented?

IMHO version numbers are like product names; important in that they're visible but unimportant in that they're decoration rather than content.

Still the version number, like a product name, carries meaning. And the most important thing you can do is avoid confusion. So here are some common expectations with respect to version numbers. To the extent that these exceptions are not met, the user will probably be confused:

Version numbers are monotonically increasing
This is probably the most obvious expectation, and at the same time the least likely to actually be true. At-a-glance, the user expects that version 2.3.5 comes after version 2.2.17, and has the same or better technology. But of course 2.3.x is a development branch, and 2.2.x is stable, and 2.3.5 actually was release back in 2004 and the 2.2 branch is still actively being worked on and 2.2.17 was released just last April and contains... well, you get the idea. You might as well just call version 2.2 "Potato" for all the meaning that the number carries. Welcome to version "Potato-17"!!

Similar Versions are Upgradeable/Compatible
If I have version 3.7 on my computer, and 3.8 comes out with all new shiny frozbots, I expect that with some upgrade or patch or whatever, my 3.7 can become 3.8 with no interruption. But if I'm on 3.7 and you release 5.2, I'm not so optimistic. Of course, I'd rather be pleasantly surprised rather than disappointed.

The first digit is significant
I wouldn't even bother to mention this if Java wasn't so prominently confusing on the matter. Unless someone told you, you would not expect that "Java 7" was actually version 1.7. And the first time you heard this, you response was almost certainly: "What? .. Why?"

Clearly the purist will say that the major version number will only change if the platform change is not backwards-compatible. But do you actually intend to drop backwards compatibility ever? Often major version revs are a marketing decision not a technical one; the Java absurdity comes from both camps having it their way at the same time, to almost comical effect.

Finally
As I just mentioned, version numbers are often as much about marketing as they are about technology. And that's OK, since that's kind of what version numbers are for: the inform you at a glance as to what's new about the software. Big number change means big functionality change. Small number change means almost no functionality change. That's what people expect. Whether it's true or not determines whether or not your version numbers carry the same meaning that your users think they do.

-- EDIT --
I forgot to mention this, but Caleb pointed it out nicely: Don't use version numbers to indicate anything important (e.g. stable/unstable) without making it otherwise explicit elsewhere. Yes, you know that the odd minor version number indicates development, but that makes one of us. Debian's "unstable" release moniker is a good example; or you could also use a totally separate product name; "Frozbot 1.2" for your product name, and "Devbot 1.3" for your development version.

If your issue is that the customer might think 1.1.2475.54387 means "something has changed after 1.1" - forget it. In my experience, virtually all customers either don't care what the lower-order components in a version mean, or they do care and understand that they are build numbers and VC revisions, which by definition can never be 0.

Slightly more general: Looking good is a valid goal, but in a business context it only matters what the person who makes the purchase decision thinks. Those people almost always fall squarely into category (a) above. I can think of no scenario where having a non-pristine build number would negatively affect the business success of a product.