The most common reason for the paper feed problem is the paper itself. If it is damp in any way you may get these symptoms. Make sure you load dry paper and "Fan" it before loading it into the cassette. Have you tried using different paper stock?
I would also check that the feed cassette is assembled correctly. Gently remove it and check for obstuctions then reassemble.
Unlikely cause may be the driver click here for a September 2005 release - a whopping 42 MB.
If all else fails take it back under guarantee.