The Collaborative International Dictionary of English v.0.48:

Graceless \Grace"less\, a.
   1. Wanting in grace or excellence; departed from, or deprived
      of, divine grace; hence, depraved; corrupt. "In a
      graceless age." --Milton.
      [1913 Webster]

   2. Unfortunate. Cf. Grace, n., 4. [Obs.] --Chaucer. --
      Grace"less*ly, adv. -- Grace"less*ness, n.

WordNet (r) 3.0 (2006):

graceless
    adj 1: lacking graciousness; "a totally graceless hostess" [syn:
           graceless, unpleasing]
    2: lacking grace; clumsy; "a graceless production of the play";
       "his stature low...his bearing ungraceful"- Sir Walter Scott
       [syn: graceless, ungraceful]
    3: lacking social polish; "too gauche to leave the room when the
       conversation became intimate"; "their excellent manners
       always made me feel gauche" [syn: gauche, graceless,
       unpolished]

Moby Thesaurus II by Grady Ward, 1.0:

91 Moby Thesaurus words for "graceless":
   Doric, all thumbs, awkward, barbarian, barbaric, barbarous,
   blunderheaded, blundering, boorish, bumbling, bungling,
   butterfingered, cacophonous, careless, clownish, clumsy,
   clumsy-fisted, coarse, crude, cumbersome, damned, doggerel,
   dysphemistic, fingers all thumbs, fumbling, gauche, gawkish, gawky,
   godless, gross, ham-fisted, ham-handed, harsh, heavy-handed,
   hulking, hulky, ill-chosen, improper, impure, in bad taste,
   inconcinnate, inconcinnous, incorrect, incorrigible, indecorous,
   inelegant, inept, infelicitous, irreclaimable, irredeemable,
   irreformable, left-hand, left-handed, lost, loutish, low, lubberly,
   lumbering, lumpish, maladroit, oafish, outlandish,
   past praying for, ponderous, reprobate, rude, shriftless, sloppy,
   stiff, tasteless, unconverted, uncourtly, uncouth, undignified,
   uneuphonious, unfelicitous, unfortunate, ungainly, ungraced,
   ungraceful, unhandy, unhappy, unpolished, unredeemable, unredeemed,
   unrefined, unregenerate, unseemly, unwieldy, vulgar, wild