Having the same issue. Tried lowering the data rate but get the same result.
What version of Premiere Elements, what computer operating system?
Just before you get the data rate message
a. Is there a check mark next to Fit Content To Available Space?
b. Before any adjustments by you, what are the readings for Space Required and Bitrate with and without the check mark next to Fit Content to Available Space.
c. What specifically did you lower the bitrate from and to?
d. What are you doing...burn to DVD-VIDEO on DVD disc, AVCHD on DVD disc?
Let us start here and then decide what next based on the details in your reply.
Any questions or need clarification, please do not hesitate to ask.