Authenticating Very Short (Sub-Block) Data
First, the fact that the data is "easy" to guess (in the sense that an attacker has a one-in-2^32 or a one-in-2^64 chance of guessing correctly) doesn't mean much if the attacker has no way of checking if his guess is correct. Or at least, it's not a problem with the cryptography.

Second, even if he does have that ability, the problem of protecting your data's secrecy is separate from the problem of protecting its authenticity. For example, it might be bad if an attacker can deduce that a message says "Yes", but it might be even worse if he can then tamper with the message so it now says "No". 

In this example, the message itself was effectively only one bit long, but it definitely would make sense to have a long (e.g., 128 bit) authentication tag!

To answer your final question: No. As long as each key is random, then periodically changing your key is not a problem. In fact, in many situations it's recommended in order to limit how much data gets compromised if an attacker manages to obtain the current key.