It seems there's some sort of problem with your database. If your forums are new and you have no old posts and topics I suggest you make a new install. I believe that's the easiest way to solve the problem.
I completely reinstalled the whole thing. I droppped the database, created a new one, reinstalled phpbb. Still gives me the same error when I make more than one category. Seems to me like this is a bug. I checked my SQL version too. I'm running mySQL 3.23.49a and I selected mysql 3.x in the menu when setting phpbb up. I thought it might be that, but apparently it wasn't.