This is a really stupid suggestion, but I think we're all running out of ideas here.
After changing the texture (increasing the resolution), did you make sure it got updated in Maya? --If you left Maya running while you went back and changed the texture, you have to explicitly tell Maya to reload the file texture. Open the Attribute Editor for that texture and click the big 'Reload File Texture' button.
You should also double-check the filename that Maya is using, make sure that your new high-res texture has the correct name.
I'm mentioning these things because it really, really looks like Maya is just using a low-res version of your texture.
Finally, I know that there are setups (for gaming, usually) which will automatically use a low res version of a texture sometimes, and higher res versions at other times. Normally the high-res version is used when the camera is close, but perhaps there's a glitch in your scene. Anyone out there know how this works, and if it might be a factor here?
Good luck.
-Steve