The Lexmark E260dn supports both PCL and Postscript. If you are using a PCL driver, try switching to the PS driver - or vice versa.
Since it supports PCL5 and Postscript you can hand edit very simple PCL5 and Postscript test pages and use Windows "lpr" command to send them without passing through Window print drivers. This can help narrow down the source of the problem.
Postscript test:
%!PS
/Helvetica 24 selectfont
100 500 moveto
(Testing 1 2 3) show
showpage
PCL5 test:
^[E^[&k2G^[&l6D^[&l0OLine 1 ..1....v....2....v....3....v....4....v....5....v....6....v....7....v....8....v....9....v....0....v....1....v....2....v....3....v....4....v....5
Line 2
3
4
5
6
7
...
80
(where ^[ is the escape character (hex 1b decimal 27))
Remote diagnosis of printing problems is hard. Get a cooperative person at the site to use the printer's control panel to print a test page and to print out the settings. They can then use an old-fashioned fax machine to send them to you.
The n in E260dn implies network-connected. Can other PCs print to the printer? If you are using VNC, you will be able to telnet to the printer and get it to show configuration settings.