Problem in BPP but not known to be in RP or co-RP Is there an example of a natural problem that's in BPP but that's not known to be in RP or co-RP?
Moved my comment here after Suresh's request.

An example of a natural problem for which we only know algorithms that require error on both sides is the following: given three algebraic circuits, decide whether exactly two of them are identical. This comes from the fact that deciding whether two algebraic circuits are identical is in co-RP.

Reference: see the post How Many Sides to Your Error? (Dec 2, 2008) about the very same question on Lance Fortnow's blog and the comments below his post for a discussion about the naturalness of the problem.