I want to start learning more AI but I'm not sure where to start. I want to start with something easy(ish) and get a solid understanding before moving onto something harder. I've done some A* before buts thats it. Where would you recommend I start and move onto? Thanks.

I recommend that you start reading books/articles and everything you can find on AI. Once you found something that looks interesting you keep searching for more material on that same thing untill you know enough to implement it.

Here some links that might get you started
ai-junkie
ai-depot
aihorizon

One thing few people seem to think about: Go to some universities' cs websites and look for
notes and assignments from an AI course. Do the assignemnts and if there's one you find interesting, play with it or use that method on another problem.

Having cracked some simple path-finding algorithms I moved into looking at Finite State Machines (FSMs). They're a relatively easy to both understand and construct if you're new to AI. Definately worth a look.

Check out this Ai-Depot Article for some help on getting started.

Path finding is not the only use of A*, its a general solver depending on the heuristic (replace the distance with some problem specific function),
for example you can use it to solve a puzzle. The path in this case are the operators to do on the puzzle to get it solved.

If you want to advance, I think the next step is to read about Alpha-Beta pruning and make a smart player for a board game (full knowledge, full probability, like chess).
If you want make the board game with creative rules and graphics and you got a nice game going!

I know these days its all about 3d and real time and first person or mmorpg, but I personaly always liked those strategic board games... sigh.

Iftah.