Not a kata issue, then?

Likely code runner server performance issues, check: https://codewars.statuspage.io/

The tests do timeout even with the following function: fib(BigInteger n) { return n; }

How do you deal with the timeout problem from there?

The main reson that the problem is ranked 3kyu is that you have to deal with the timeout problem.

I've got the same problem in Java

I'm guessing you're doing it in Java?

EDIT:
When I tested in Java, I also got the same error?

Either your solution isn't optimised or it's an error with codewars. There's no need to create an issue over it, you can debug your inputs by printing them. It's important to ntoe you can pass the normal test cases but still have an inefficient solution.