Running Linux on Windows 8 computers is entirely possible. Who told you otherwise? Only in a few cases one had problems with secure boot and UEFI. Most computers have a UEFI option to turn this off (look for legacy boot etc...).
Browse the Ubuntu forums,
http://www.ubuntu.com/certification/ or on the askubuntu.com website if the model you are interested in is in fact usable with Ubuntu and/or if there are any issues.
Everything that boots Ubuntu should work with Navigatrix as the later is based on the former.
I usually bring a usb thumbdrive with a Navigatrix/ Ubuntu live system on it into the shop and boot from it. This way I see immediately if there are any driver issues.
HTH,
Christian