Also: both skillsets (UX and visual design) are empirically testable for usability.
That's the one-note-flute Jakob Nielsen's been composing orchestras with successfully for over 17 years on his Use-IT site: http://www.useit.com/
As has been noted: Nielsen never created a beautiful thing in his life, but damned if they haven't been usable.
In the field of web/app/interaction development, just as you say this largely comes down to the two disciplines you identified: Visual Design and User Experience.
In other fields, such as architecture or industrial design, the problem solving/systemic arrangement side includes additional concerns such as structural integrity, physical usefulness, manufacturability, maintainability, etc.
(And further, architecture places weight on the expression of values, which isn't as much of a concern in screen/interaction or industrial design.)
I think that with a bit of innate talent, both sides of this duality can be mastered and personal improvements made. It really comes down to practice, which in the end tends to be proportional to enjoyment and passion.
Lastly, it's the latter half of this duality that is somewhat similar to coding, or more accurately "pseudo-coding". It's not necessarily an effortless transition however: I can design logical systems and arrangements ADED, but attempting to translate that aptitude into coding skills is slow and painful.
If I'm working on user research I need to understand the people (user groups) who use the product and how they use it. If I'm working on interaction design, I need to understand how each interaction takes place, what problem it's solving, what that means for the user, and how it effects anything else. If I'm working on visuals/graphics, I need to design the product/features/interactions in an aesthetically pleasing way that still targets the user groups.
So UX will guide you towards what features are important and ways of exposing those features so the end user has the best experience. UX also tends to focus on testing assumptions.
Visual design will guide you towards making sure the elements on the page are aestheticly pleasing and that they communicate what is trying to communicated. Google is famous for testing it's shade of blue, but, IMO, great design can't be tested, but rather comes from a designer understanding her audience and the story she is trying to tell.
Don't get me wrong, usability testing is incredibly important. Every programmer can tell you how much they learned the first time they watched an uncoached newbie try out their software. And even with those paradigm-shifting design changes, you can and should test that the results are really an improvement. But you can't make big important changes by measuring the impact of every little detail.
That is the sort of skill it takes to be a great designer IMHO.
Visual Design is one of those things where the best designers do have a innate artistic ability. There is a certain level of talent in this area which you're just born with.
UX however is a skill which can be taught and learned and is a phenomenal skill for a product guy, learning to do Information Architecture, UX etc. is very doable.
BTW Not all visual designers are good at UX. Those that are talented at both aspects of design are pretty much unicorns.
A spot to get started http://www.uxforthemasses.com/ux-books/