I agree with increasing the width, but I would like to also point out a couple of things:
Firstly, I never expect people to adjust their settings in ways that would result in improvements, so for the dial-up users, it still seems like a nice idea to have some restrictions on signatures; however, they'd be better dealt with using file size, not image size.
Secondly, I'd be a bit wary about increasing the signature width past 500 pixels, because at that point, it has an effect on the layout (sans images, once the message area gets narrower than 495 pixels, a horizontal scrollbar will appear, primarily because the top menu consumes 700 pixels).
EDIT: And while I'm at it, the vertical size limit would be better off applied to the entire signature, rather than just the images.