FChris, for many people it takes a long time to be comfortable with barre chords.
In my experience the most crucial aspect has usually been thumb position. Most people benefit from having their thumb perpendicular to the neck and aligning the thumb opposite the middle 2 fingers - this allows comfortable grip and maximum finger span.
Also try practicing down around the 5th to 7th fret where it is a bit easier to build your confidence.
It can take up to a year or so to be able to confidently switch from open chord shapes to variations (maj, min, 7th) on E & A barre chord shapes (most commonly used) and between shapes.
One thing I did was use E & A barres to play songs that I'd learned as simple open chords. This had 2 effects - I quickly improved as it was a way of doing interesting mass practice; and I learned the notes on the 6th and 5th string (root notes) which till that time I'd struggled a bit with.