CFE does not load vmlinux.lz - TFTP error 3


I'm trying to boot vmlinux.lz on a BCM63xx board from TFTP, but for some reason it does not boot:

CFE> r
Retry loading it as a compressed image.
Loading ...
*** command status = 0

The TFTP conversation looks like this:

Router -> TFTP: read request, file vmlinux.lz
TFTP -> Router: sends Block 1 (512 bytes)
Router -> TFTP: error code 3 (disk full or allocation failed), message "transfer canceled"

If I understand correctly (from this post), CFE checks the first block is NOT an ELF and should continue to load LZMA compressed image. But that does not happen for some reason.
The vmlinux.lz has been extracted from the original OEM firmware

Has anyone seen this? What may be wrong?