It definitely can't be a cookie issue. There are only 2 places that exact text string is used and both of those come when comparing a check on their U_Banned field.
Try this. Run this command from the Database Tools -> SQL Command box:
select U_Banned from w3t_Users where U_Username='theirusername'
Replace theirusername with their actual display name.