Brother HL-1110 MEMORY FULL errors when printing.

[MrJinxed55]

Printing test pages just works fine, due to them being very limited in size.

But when having the printer set to 600 DPI, and trying to print a 300 DPI scan, I get the blinking orange LED, and when printing out printer settings, I see that the MEMORY FULL count has gone up.

Trying to print a PS that is based on an image creates this in the CUPS printer queue:

559 K should fit in the 1 MB memorey the printer has.

The command I use to convert the image to PS is the follwing:
convert TMP_DIR/scan_{DATE_T}.tiff -colorspace Gray -density 300 -compress lzw -brightness-contrast 5x0 PRINT_DIR/scan_{DATE_T}.ps

I made 2nd try using tiff -> pdf -> ps
CUPS got that the size was 568 K, but still fails with MEMORY FULL error.

Here are the commands I ran to do the conversions:
convert TMP_DIR/scan_{DATE_T}.tiff TMP_DIR/scan_{DATE_T}.pdf
gs -sDEVICE=ps2write -dLanguageLevel=3 -dNOPAUSE -dBATCH -sOutputFile=PRINT_DIR/scan_{DATE_T}.ps TMP_DIR/scan_{DATE_T}.pdf

I managed to get around this problem once, by setting:
lpadmin -p <print_queue> -o usb-unidir-default=true

But alas, it does not help this time.

[MrJinxed55]

PS_test_files.zip

Both PS files I tried to print.