Were the effects prepared in HD, though? That's the real issue. Transfering from 35mm to HD isn't cheap, but since 35mm has many times the level of detail as HD, it's not the problem. The problem is the resolution the visual effects were prepared in.
The same exists for TNG--it was shot on 35mm throughout the entire run, but the effects were produced on video and the episodes were mastered on video. So even if they returned to the original elements, the effects would still be at NTSC resolution.