First of all, what does his diet consist of? When I feed my beardie the dry pellets, (of which he only eats the green ones) his BM's come out BRIGHT green. If you are feeding him pellets that are red, I could imagion that you are experiencing the same problem. Furthermore, with my experience with various species of tropical geckos, when feeding them babyfoods, some of them cause the geckos BM's to un-natural colors.
If none of this applies to you, then I would agree that you take your pet to a qualified herp vet. Hope all goes well.
~Nick