1) deine partition ist aber nicht verschlüsselt?
2) RL3 bedeutet runlevel 3, also ohne graphische umgebung nur konsole. Wenn also das problem auch dann besteht kann man als ursache die gesamte graphikumgebung (proprietäre treiber und je nach DE auch kde, kdm, gdm usw) ausschliessen.
Um nach RL3 zu booten mußt du in Grub in den bearbeitungsmodus wechseln ( mit "e" für edit) und als zusätzlichen startparameter eine "3" anhängen (ohne "").
3) DE = Desktop Environment = graphische oberfäche, welche in RL3 ( du erinnerst dich?) nicht geladen wird.
4) es gibt bei RH (redhead) einen relativ frischen bugreport vom 2013-04-18
https://bugzilla.redhat.com/show_bug.cgi?id=953414, der ein ähnliches problem beschreibt. Ich bin der meinung, dass auf deinem system ein bug ausgelöst wird (remount beim herunterfahren, warum?). Wenn du noch nicht mit dem Debiantool "reportbug" vertraut bist solltest du dich einmal durcharbeiten und damit den fehler möglichst auf englisch bei Debian mit beschreibung (vor/nach d-u) melden.