Yes, this is a drawback of using // @run-at document-start.  @required scripts that attempt to manipulate the DOM may throw errors.  (But many @required libraries are fine, as they merely load tools that are activated by your code later).
You can work around this by using @resource, eval(), and by monitoring readyState. Like so:
// ==UserScript==
// @name        _Using DOM-manipulating libraries with run-at start
// @include     http://YOUR_SERVER/YOUR_PATH/*
// @run-at      document-start
// @resource    jQ_src https://ajax.googleapis.com/ajax/libs/jquery/1.7.2/jquery.js
// ==/UserScript==
var jQ_src  = GM_getResourceText ("jQ_src");
window.addEventListener ("readystatechange", FireWhenReady, true);
function FireWhenReady () {
    this.fired  = this.fired || false;
    if (    document.readyState != "uninitialized"
        &&  document.readyState != "loading"
        &&  ! this.fired
    ) {
        this.fired = true;
        eval (jQ_src);
        $(document).ready (DoStuff);
    }
}
function DoStuff () {
    //--- Where this next paragraph appears can give you an idea of the delays involved...
    $("body").append ('<p style="background:yellow;">Hello from quick-start jQuery!</p>');
}
Important! For libraries like jQuery, there is not much point in using @run-at document-start, because jQuery won't let you do anything until $(document).ready() anyway, and this is when Greasemonkey fires by default.
Loading jQuery early buys you nothing, because then you must explicitly use $(document).ready() (or one of the shortcut forms).  You may have other reasons to use @run-at document-start, and then also want to use jQuery later, perhaps.