I’m going to assume you’re using Premiere Pro CS4?
I found this problem and a workaround when I first got Premiere Pro CS4, back in December last year.
Lately, though, I haven’t had the problem, so I suspect that if you download updates for Premiere, it should be OK.
In the meantime, the workaround I found was this:
The transitions work fine until you render the sequence, at which stage the Cross-Dissolve disappears entirely, and becomes a plain cut.
The workaround is place a single keyframe of 99% Opacity on your clip – and Presto! – the transition is back in all its glory.
I hope this saves your sanity!