It sounds like your IO LEFs don't have physical pins defined. If you zoom in to the I/O cell, do you see pin shapes? You already said you checked the LEF...
To try routing a net by hand, see the "Editing Wires" chapter in the User Guide.
Are those nets considered "SPECIAL" nets? (If you output a DEF, do you find these nets in the NETS section, or the SPECIALNETS section?)
Try these things and see what happens next - hard to debug from a distance, but hopefully we can get to the bottom of it.