I had this problem yesterday, what worked (for me) was unchecking "Reserved Slots Visible" in the menu and restarting the server. I contacted my host about it and they said it most likely had to do with an addon affecting the "sv_visiblemaxplayers" CVar. The server isn't full just the Server Browser is displaying it as full, people can still connect with 'connect <server IP>'. Hope that helps you.
Edit: You said you tried with visible slots... Did you try restarting? Try messing around with the maximum reserved slots.