This situation may be due to different interactions of the fluorophore (tryptophan?) with urea versus with GdmCl. In both cases, the red shift is indicative of exposure of the fluorophore to a more polar environment. The fluorescence increase upon urea denaturation may be the result of the fact that the fluorophore is somewhat quenched in the folded state by interactions with other residues, and this quenching is relieved when the protein is unfolded. The fluorescence decrease upon GdmCl denaturation is probably due to quenching of the fluorophore by GdmCl.

If you are looking at Trp fluorescence then you could check it fairly quickly by comparing the fluorescence of the individual amino acid Trp dissolved in both final buffers. But it sounds right. The fluorescence changes because the local environment of the aromatic side chain changes - and the local environment of a solution exposed tryptophan will be different between a concentrated solution of urea and Gdm. 

Chemistry tells us that when free Trp is transferred from a non-polar medium to a polar medium, there is a decrease in fluorescence intensity with a read shift. This is the reason we expect that exposure of a buried Trp residue on denaturation will lead to a decrease in fluorescence intensity with a read shift. My experience is that during protein denaturation the rule of chemistry is always followed as for as the shift in wavelength is concerned but it is not always followed in the case of fluorescence intensity. As pointed out by other colleagues, Trp fluorescence intensity depends on many factors. Hence its observed intensity is not simple to interpret in many cases.

Although urea and GdmCl are both strong denaturants and induce the same denatured state of a protein in almost all cases, mechanism of denaturation may differ due to difference in their chemical nature. There are many examples in the literature that show that mechanism of of urea-induced denaturation is different from that of GdmCl-induced denation.

How far did you go in terms of urea and GdmCl concentrations? Are you sure that both transitions are completed? Does your protein unfold through intermediate state? For many globular proteins, the use of GdmCl allows decoupling native state intermediate (molten globule) state and intermediate state unfolded state transitions, whereas in urea these transitions typically overlap. Also, GdmCl-induced curves are typically noticeably steeper than urea-induced unfolding curves. To verify complete unfolding mechanism of your protein you should use more than one technique. For example, near- and far-UV CD are typically used to detect changes in tertiary and secondary structures, respectively.  

Obv GdmCl is charged and urea isn't.

Did you do unfolding equilibria experiments or did you try to denaturate the protein with high concentration of denaturant? In first case you can fit the fluorescence intensity with the concentration of denaturant to observe the transition folded/unfolded (e.g. two step transition). I agree with Vladimir you could try to use complementary techiniques for example FAR-UV CD spectroscopy. Be carefull because at wavelengths