Server-side you have to use Java's Random, not GWT's *client* Random
(which, obviously is for client-side code and defers to JavaScript on
way or another).
The exception you get is because GWT's Random.nextInt is a JSNI
method, i.e. a "native" Java method with some special comment in the
source so that the GWTCompiler knows how to transform it to
JavaScript. Because it is marked "native", a JVM tries to find its
implementation in native libraries, and in this case it doesn't find
any.