Possibly Magi-Nation.
The series centers on a young boy from Earth who travels to the Moonlands, a mystical world full of monsters and such, thanks to a ring given to him by his grandfather, who previously traveled there.
His companion is Furok, which sounds similar to Brock, and he is blue with horns, and at least at one point, as seen in this image, flies:
The plot you describe where he's accused of stealing the monster seems to occur in the episode "The Depths of Courage" according to a fan wiki synopsis:
When Tony summons Furok, the Orotheans gather in amazement, they tell him that Furok is the same one used by the Magi who vanquished the Cawh, the magi was Spencer Jones, Tony's Grandfather. An Orothean named Borse accuses Tony of stealing Furok and challenges him. Borse defeats Tony with his Allio and declares Tony an imposter.
