The title is a reference to the often-mistranslated quotation commonly attributed to Hermann Göring -- "When I hear the word 'culture', that's when I reach for my revolver" -- the actual quote is "Wenn ich Kultur höre ... entsichere ich meinen Browning!" This translates as: "Whenever I hear [the word] 'culture'... I remove the safety from my Browning!" In fact, it is a line uttered by the character Thiemann in Act 1, Scene 1 of the play Schlageter, written by Hanns Johst. The association with Nazism is appropriate, as the play was first performed in April 1933, in honor of Hitler's birthday. 
Catherine Wheel recorded a version of "That's When I Reach for My Revolver" for their 1992 EP 30 Century Man. Notably, the song also features slightly altered lyrics from the original, such as the replacement of "The spirit fights to find its way" with "That feeling passes by this way".
The original version of "That's When I Reach for My Revolver" had a substantially different lyric. Among which is "Tonight the sky is empty/But that is nothing new/Its dead eyes look upon us/And they tell me we're nothing but slaves." Moby changed the lyrics, and the change most noticeable is the third line ("Instead they look upon us").
Moby provided an alternate vocal track to permit airplay on MTV: with subdued lyrics, the video version was retitled as "That's When I Realize It's Over".
Graham Coxon recorded a version of "That's When I Reach for My Revolver" for his second album The Golden D, released in 2000. This song was never released as a single but is sometimes used in Coxon's live sets.