We present the results of new rest-frame far-IR observations of the z = 4.25 radio galaxy 8C 1435 + 635, which not only confirm that it contains an enormous quantity of dust (as first inferred from its millimeter-wave detection by Ivison in 1995), but also allow the first meaningful constraints to be placed on the mass of this dust and associated gas. The new measurements consist of (1) clear detections of submillimeter continuum emission at lambda(obs) = 450 and 850 mu m obtained with the new submillimeter bolometer array, SCUBA, on the James Clerk Maxwell Telescope, (2) continuum upper limits at lambda(obs) = 350, 750, and 175 mu m obtained with SCUBA and the PHT far-IR camera aboard the Infrared Space Observatory, and (3) a sensitive upper limit on the CO (4-3) line flux obtained with the IRAM 30 m Millimeter Radio Telescope. The resulting rest-frame 33-238 mu m continuum coverage allows us to deduce that 2 x 10(8) M-circle dot of dust at a temperature of 40 +/- 5 K is responsible for the observed millimeter/ submillimeter emission. Using our CO upper limit, which constrains M-H2/M-d to less than 950, we go on to calculate robust limits on the total gas reserves (H-2 + H I), which are thereby constrained to between 4 x 10(10) and 1.2 x 10(12) M-circle dot. The submillimeter properties of 8C 1435 + 635 are thus strikingly similar to those of the z = 3.80 radio galaxy 4C 41.17, the only other high-redshift galaxy detected to date at submillimeter wavelengths whose properties appear not to be exaggerated by gravitational lensing. The inferred gas masses of both objects are sufficiently large to suggest that the formative starbursts of massive elliptical galaxies are still in progress at z similar or equal to 4. Observations of complete samples of radio galaxies spanning a range of redshifts and radio luminosities will be required to determine whether the spectacular far-IR properties of 8C 1435 + 635 and 4C 41.17 are primarily due to their extreme redshifts or to their extreme radio luminosities.