I've done some substantial further testing.
It worked on examples of the following systems:
Ubuntu 12.04 64-bit with Oracle 7u6,
Ubuntu 12.04 64-bit with Oracle 7u10 (same machine as previous),
Ubuntu 12.04 32-bit with Oracle 6u14,
Ubuntu 12.04 32-bit with Oracle 7u10 (same as previous),
Ubuntu 12.04 32-bit with OpenJDK 6 (same as previous),
Windows XP (!) with Oracle Java 6 (unknown update)
Windows 7 with Oracle Java 7u9,
Windows 7 with Oracle Java 7u10.
It did not work on some examples of:
Ubuntu 9.04 32-bit with Oracle 7u10,
Ubuntu 12.04 64-bit with Oracle 7u10,
Ubuntu 12.04 64-bit with OpenJDK 7 (same machine as previous line),
Windows Vista with Oracle Java 7u8,
Windows Vista with Oracle Java 7u10,
Windows 7 with Oracle Java 7u10.
In particular, the last entry on each list was the exact same system at different times. It failed to work, and later worked without changing settings. The Vista entries were also the same machine, but after uninstalling 7u8 and freshly installing 7u10.
Edit: So yes, it could be a problem with all those Java installations. If so, it seems likely to be a widespread type of problem with Java installations in general, and not a specific problem with a single person's Java installation.