Default PDF Page Formats aren't respected after upgrade to 4.5.8
I did try creating an example against http://wp45.demo.civicrm.org/ - It worked fine.
Even I have worked in previous version (4.4). I haven’t got any issue at all.
So, please try setting the table width = 100% - this should work correctly.

Example: from Demo (used message template: “Sample CivicMail Newsletter Template”).

Had a table setting like below 
table bgcolor="#ffffff" cellpadding="0" cellspacing="0" width="612"

Just change the above line to 
table bgcolor="#ffffff" cellpadding="0" cellspacing="0" width="100%"

This gave me a correct output – with proper margin – I guess this Helps!!!