You'll need to stick a width of 100% in there somewhere.
width="100%"
Like this maybe...
Code:
<table width="100%" border="0" cellpadding="0" cellspacing="0" align="center" background="yourstretchy background bit.jpg">
<tr>
<td align="left"><img src="http://www.liverpoolway.co.uk/images/leftbit.gif" border="0" /></td>
<td align="right"><img src="http://www.liverpoolway.co.uk/images/rightbit.gif" border="0" /></td>
</tr>
</table>
Unless any of this is in the CSS.