Here's what happens: you create a new SharePoint App in Visual Studio and the first thing it asks for is a SharePoint site that you are going to use for debugging. You're all excited about this new cloud thingy so naturally you point it at the Office 365 subscription you got free with your MSDN subscription, or maybe a trial site. Then you realise Office 365 isn't going to work because you just lost your connection to the Internet for the sixth time today so you decide to use the SharePoint VM you have on your machine. That's when you get the error and, hey, I thought SharePoint 2013 was version 15 anyway - what's up with that?
The problem is that at some point they bumped the version of SharePoint Online in Office 365 to 16. It isn't really SharePoint 2013 anymore, it's... the cloud. It gets updates every couple of weeks. They've moved on. In the old world SharePoint Online would lag behind the packaged product but all that has changed; now it's the other way around. (By the way, if you have a recent version of Visual Studio you will notice that the "autohosted" option is gone in every sense - as I say; they've moved on).
So if you create a Visual Studio project against Office 365 it will set the TargetOfficeVersion property to 16.0. You can see this in the project properties under the SharePoint tab. When you change the target SharePoint site it doesn't update this automatically - you will need to change this also.
You might not see it if you have an older version of Visual Studio but you can manually edit it in the .csproj file at the line:
Changing it from 16.0 to 15.0 should have the same effect, although it is possible that you may need to update some references if you do it this way.