Hi Andrew,
I've used the same paper in my 3800 with no problems. I did have the same problem with some 13x19 size sheets that had a definite curl to them - the curl was along the sides where you are having problems. I made sure to curl the paper the other way and the problem stopped. Hopefully your cure is as simple as that.
Dave
Bookmarks