There are two different errors for "too large." There's weight (file size) or dimensions. Or you might be dealing w/both in which case you'll get one error at a time. W/either, uploading to tinypic will give you a URL to use but won't change dimensions or file size. It's better to manually fix your image then upload it to tinypic (don't use there options). So you'll need to fix that with an image program or online image resize tool of some sort. Nothing fancy needed. I use Irfanview
a lot for that kind of stuff. It's free and pretty simple to resample/resize images or change the file type.
For dimensions, just keep it at 125 x 125 px. If you're getting the weight error, it should say what is allowed (don't know that off hand) and you'll need to reduce it. Sometimes just changing it from a jpg to gif or png is all you need to do. But, usually, if your image is only 125 x 125 px, it shouldn't be to heavy and will clear both errors.
But mostly (as for most error questions like this).... please see the FAQ
on this. The banner errors are all explained there in depth. Links, examples sizes, descriptions, etc.