Hmm, funny this would be mentioned (inside joke).
Cafe signature size limits are supposed be under 10240 bytes. You shouldn't have been able to use larger ones than that before anyway. Most (well, dang near all the time if you're dealing with a signature of at least 300x100 pixels) times when creating a signature, you have to "optimize" the JPEG file in order to make it fit. Optimizing reduces the quality of your images slightly, but it makes them smaller to reduce loading time (mainly for the dialup user). If you (or whoever does your signatures) use Photoshop, by using the "Save For Web" command you can optimize your images. Just fiddle around with the settings until it is under 10KB in size. Normally, this is accomplished by dragging the quality bar to around 40 (Medium) instead of 80 (High).
If it's still too big, either lower the quality bar more (not recommended because the pictures will look really bad), take some of your artwork out, blur the background more, or reduce the overall size of the image (easiest way).
I hope that helps you out. There are probably other threads in the Fantasy Logos forum that can help you out.
If you need further help, just post the link to your image, and I can optimize it for you.