I am trying to write an ftp client that will navigate and fetch files
from a MVS system. After logging in, when I send the REST command I
get the message "Restart requires EBCDIC data type". I solved this by
sending "TYPE E". Then I get "Restart requires Block or Compressed
transfer mode" I also solve this by sending "MODE B". When I send the
command "REST xxxx", xxxx being a number indicating the number of
bytes to skip, I get "500 Invalid restart parameter". The welcome
message I get from the server is "220-FTPD1 IBM FTP CS V2R8 at
XXXXX.COM.YY, 12:06:36 on 2002-07-17.", if you should need it to
figure out the version and make of the ftp server.
How can I overcome this problem and use REST to resume downloads?

The FTP protocol specification, RFC959 [1] (with some additions and
clarifications in RFC1123 [2]), clearly states that an FTP server is
not required to implement the REST command. Although the error message
you are getting, seem to indicate that the command is indeed
supported, but you are using it wrong.

It seems like you are wrong in assuming that the argument to REST is
the number of bytes to skip from the beginning of the file. The FTP
protocol specifies that in block transfer mode, the server gives out
special markers at regular intervals. The value of these markers can
then be used to specify a position to continue downloading from. So it
is up to the server to give out arbitrary markers, and for the client
to use these markers when resuming downloads.

There is also a IETF draft specification about "Extensions to FTP" [3]
describing the more intuitive resume mechanism for stream mode
transfers, where you give the offset in bytes. Unfortunately your FTP
server is not modern enough to supoprt that.

Hope these pointers help you get a working implementation!

References
[1] http://www.faqs.org/rfcs/rfc959.html
[2] http://www.faqs.org/rfcs/rfc1123.html
[3] http://www.ietf.org/internet-drafts/draft-ietf-ftpext-mlst-15.txt