The problem with 26650 batteries is they're not normally intended to be interchangeable like AA batteries. They are most often found with solder tabs spot welded to the ends and either hard wired into a battery pack (such as for a laptop battery) or soldered direct to a PCB.
Being rechargeable they don't need replacing, so there is no need to add the expense of a battery holder.
However, that doesn't mean it's impossible.
You can buy PCB mount contacts for AA batteries, which are similar in size, such as these: http://uk.farnell.com/keystone/590/battery-holder-aa-n-1way/dp/1339844 and build up your own battery holder on a PCB. You may need to adjust the sprung leaf a little to get to the right level for the battery contact, but it's certainly a possibility. You would, of course, need some side support to keep the battery in place, but I'm sure a creative mind like yours could come up with something that would work.
I suspect that you are connecting Aref to the regulator output.
While you have sufficient voltage, and the regulator provides the correct (i.e. expected) voltage, you get correct readings.
When the battery falls below a limit, the output at the regulator falls, and will always be the input V minus its drop. The ADC will always read the same voltage (since regulator output = Aref = Battery - Reg. Drop), which happens to be a higher ADC value than before this condition.
You need a better reference voltage at Aref. You can, for example, use a Zener with a drop less than 2.8V, and a voltage divider to feed the ADC.
Update: (Regarding your comment) You should add a better reference voltage to Aref. Since you observe the problem it is a good practice to fix it. Your arduino the way it works now cannot tell whether the battery is dead or fully charged, which is not a good idea.
Another point is that you risk damaging your arduino, as you are bringing Aref above Vcc. There is limit for this (I can't remember, check datasheet).
Finally is is also a bad practice to rely on something you observed (and it is not a guaranteed specification), since it may soon behave differently. Save yourself from headaches, and design following good practices.
Best Answer
They're much bigger than an AA let alone an AAA battery. Check the dimensions. You can buy 18650 holders (the batteries themselves are actually a bit more difficult to get ahold of from reputable sources).
AAA: 44mm long x 10mm\$\phi\$
18650: 64.8mm long (or longer) x 18.3mm\$\phi\$
There is an additional complication- the 18650s are made with or without protection PCBs which add something like a couple mm to the length.