I’ll have to echo what J.D said: practice makes perfect. I’m not too great at fighters, but I’ve recently been starting to practice a fair bit with SSF4:AE, and I think I’ve come quite a long way in being able to pull off some cool moves with only an hour or two of practice a day (and not even every day). Stuff as simple as Guy’s 1st Target Combo was pretty hard for me to pull off at first, but since I got more familiar with the timing I’ve been able to do it pretty well. That thinking can be applied to pretty much any combo.
And if we’re talking about the slightly trickier stuff (as you said, FADC into an Ultra), I had similar trouble with Cody’s H. Ruffian Kick->FADC->Ultra 1. The reason is that I pull off the FADC forward, then I panic and effectively slam my face into the stick. The point is, you may need to take a breather every now and then and approach the combo with renewed focus. When I do that, I can pull off the stuff I intend to do on pretty much the first or second try. And if I can’t, then I at least make good strides in learning how to get through the trickiest parts. Having a calm mind is pretty important to getting the timing and inputs down for pretty much anything.
As J.D said, practice the Ultra by itself so you can get familiar with the motion and then use it as part of a combo. It does seem like you may be rushing the motion out in a panic, as I tend to do. Being new to a stick probably doesn’t help either, but you’ll get used to it with time. At this point, maybe just practicing the basics with a stick is a good thing to do. Once you do that, you’ll be able to use what you already know to good effect. Try going through the character Trials, that helped sharpen me up pretty well. It’s always good to practice even the most basic stuff every now and then.