From what I can gather (having not seen the show) Bravest Warriors is set in 3085. The oldest inhabitants of Ooo in Adventure Time are Marceline and Simon, and Marceline is 1003 years of age. (
Her age was the answer to one of Gaia Online's ten trivia contests to answer to try to win a first season DVD set. --Adventure time wiki)
This I believe puts the time line of Ooo to be ~995 years from present day give or take.
This would mean that Adventure Time is set around 3009 leaving 76 years between the two series, which seems perfectly cromulant.
The only last thing is that in Bravest Warriors I believe they can cross dimensions and time travel . So even if the two settings re not the same, it's not beyond the creators ability to mix the two with some light hand waving.