This mostly just comes with experience. When I started programming (which was well before the internet mind you), my solutions to solving problems were horrible. I had limited knowledge of HOW to solve the problems, so I solved them the only way I knew, which was massive global variables, goto's, and other ugly practices.

But, I kept working at it, kept reading books and I had a friend who programmed as well, and we would bounce ideas off each other (what the internet is good for these days). Eventually, i got better at it, learned new ways to solve problems, and I could make new things.

So, I'd say stick with it. It's not going to be easy, but eventually, things will start to "click" and you'll woner why you didn't think of that before. Good luck!

When you're trying to come up with a solution to a problem, don't immediately start thinking in code.
Your code has to be a tool to implement your solution, not a tool to come up with a solution.

The first thing you should do when trying to solve a problem is breaking it down into smaller and more manageable sub-problems.
For tic-tac-toe you have several simple aspects: You'll require a representation of your game board and a way to manage your game logic (ie. managing who's turn it is, checking for winning conditions, etc.)

A potential breakdown for a game board could look something like this:
-You need a game board, containing 9 squares. This means you'll need:
-A way to represent a square. Each square can hold 2 values, so you'll potentially need:
-A simple structure which can represent these values

So now you have a very basic and manageable overview of what you need to implement for a visual representation of tic-tac-toe.
Now you can do a similar breakdown for your game logic aspects.

Once you have these two major aspects figured out you'll have a complete overview of your program. Now you can start thinking about how you want to implement your solutions in your language of choice.

I struggle to figure out HOW to solve it, like what variables, etc are needed.

I find this common lament kinda odd. I never have run into this. I never really have problems thinking about how a syntax element might be used to solve problems... Granted, what I come up with (especially starting out) isn't always the best or most practical solution for things but it's a solution.

I dunno... did I just play with too many Lego's as a child?

I understand what the syntax for the languages do, how to use them, etc.

Problem is. When it comes to solving a problem (ie making a simple console game of tic-tac-toe). I struggle to figure out HOW to solve it, like what variables, etc are needed. Is there a way around this? I have a book called "How to Think Like A Programmer". But is this really something I can work around?

Problemsolving is what programming is all about, the language is just a tool you use to express your solution.
You get better at problemsolving with practice, (start with simple problems and work your way up).
The key to solving all big problems is to break them down into smaller, more managable problems.

... the language is just a tool you use to express your solution.

This is the key here. If you know how to solve the problem in your head, or on paper then you just need to learn to slow down your thinking and break it into the smallest possible logical steps. Then just turn each of those steps into a piece of code.

For instance when I think about playing a game of tic-tac-toe:

• There's a 3x3 board made up of blank spaces. (Need to think of a way to express the board in the language - and a way to display it to the players)
  
• I put an X in a space every time I get a turn, and my opponent puts a O in a space every time they get a turn. (Need to think of a way to place different markers.)
  
• Our turns alternate back and forth between us. (need to set up a sequence that alternates turns)
  
• Eventually either the board is full or else one of us gets 3 of our symbol in a row and therefore wins. (need to be able to check for end conditions)
  

Another thing that helps a lot is to try not to think about your program as 'what's happening on the screen'.

Try to implement your solution in a sort of 'theoretical space' that's just pure logic. Then make a way to represent that logic on the screen. I see a lot of new programmers try to form their logic around their presentation rather than the other way around and this causes no end of confusion. Think about it like 'The Matrix'. You are 'The One'. The players of your game see the illusion - the graphics on the screen - but you see the truth - that the graphics are just a lie that represent a hidden reality. Develop that reality in the world of pure logic and then teach it to generate graphics.

Feel free to take a whack at stuff and then post it here if it's not working out and ask questions about it. As long as people see that you're thinking about things they'll often give you a lot of advice about structure and such.

Hope that helps. Good luck.

Actually, if you don't mind dealing with LISP a little bit you can watch some SiCP videos here. I don't know if that's what you need, but maybe it will help you out. If you start watching it and it doesn't make any sense then just close it. No reason to add confusion at this point - you can come back to it later.

did I just play with too many Lego's as a child?

Impossible.

And I think your progression is a textbook process for skill advancement and experience programming: new programmers rapidly learn how to use the tools, but their solution is brute-force or inelegant and often resource-wasteful. The more practice (with a paradigm or problem domain) the better the solutions become. Just like a pianist knows how to hit the keys, but a beginner's music sounds all clunky and off compared to a master.

OP: it just takes time and practice. But mostly practice. If you're not attempting solutions and writing code, you're not making any headway.

Do you have the free time to enroll in a Data Structures or Algorithms class at a local college? Once you know what all the tools in the tool-box do, its easier to pick the right ones to solve problems.