My wi-fi only K Touch has all kinds of problems connecting to my network, whereas my K3 has no issue at all. Go figure.
Try restarting your wireless network. Then try connecting the Kindle again. My Kindle Touch always connects once I reset my modem.