If you are working out that much, some denser carbohydrates would be neutral or helpful to you. Consider starting at about a ~1/2lb sweet potato per day. If that makes you feel good generally, and weight loss slows a bit, consider branching out into other ones: yams, cassava, etc.

At 6ft tall, you are likely reaching or have reached "an ideal weight."

Many people here wish they had your problems. :-) Great job, and good luck!

In addition to some carbs as greymouser suggests, consider adding fatty meat (or butter/coconut oil) more frequently. Why? Muscle cells (myocytes) are made mostly from FAT, not protein. (Hat tip Paul Jaminet). Without plenty of fat, you cannot build more muscle - of course, protein is also required.

Anyone who knows anything about gaining or getting bigger says you need to do three things:
1. Work out heavy/high intensity - sends the growth message to your body.
2. Rest/sleep/recover - this is when you actually grow.
3. Eat! You simply can't grow if you don't eat enough.

In the words of Mrs. Claus: "Eat, Santa eat!"

Or from My Big Fat Greek Wedding:
Maria Portokalos: Ian, are you hungry?
Ian Miller: Uh no, I already ate.
Maria Portokalos: Okay, I make you something.

Edit:

You seem to be afraid of saturated fat, which is only normal, considering the message that the media has been blaring for 40+ years. My counsel would be to educate yourself further into the truth of the matter. Some things for you to consider:

Meta-analysis of prospective cohort studies evaluating the association of saturated fat with cardiovascular disease http://www.ajcn.org/content/91/3/535.short "A meta-analysis of prospective epidemiologic studies showed that there is no significant evidence for concluding that dietary saturated fat is associated with an increased risk of CHD or CVD."

Chris Masterjohn on cholesterol: http://www.cholesterol-and-health.com/

Dr. Eades review of Dr Malcom Kendrick's book "The Great Chlesterol Con" http://www.proteinpower.com/drmike/statins/646/

Anthony Colpo has a book by the same title

Gary Taubes "Good Calories, Bad Calories" pretty much destroys the diet-heart hypothesis (that eating saturated fat or cholesterol has any association with heart disease)

"Fat and Cholesterol are Good for You" by Uffe Ravskonov

And from Tom Naughton, some no-bologna facts: http://www.fathead-movie.com/index.php/no-bologna-facts/

"I work out 3-4 days a week lifting weights and while I haven't lost any strength, it doesn't look like I've gained any muscle either during the past 3 months"

You might be over training. It would help if you posted your exact workouts.

I agree with Dave on this one, you want to eat more fat. Remember that when you are working out in any variety you need fuel. In a paleo diet fuel comes from fat not carbs, so through in some eggs, oils and ribeye (which helps on the protein)

I would also look into your workouts. It's OK if you work out a lot but keep the workouts short (30 -45 min) I would tell you to consider HIIT training. High intensity in a short amount of time. This will trigger your muscles faster than lifting or a longer period. Max out your weights.

If you tighten up those workouts, and eat more fat you should be good to go. I also recommend that you eat a gram of protein for every pound of body weight to see muscle gain. I use a protein called Carnivore, which is made from beef isolate, not only does it work really well and have a solid amino acid balance sheet, it is the best tasting supplement out there. (chocolate)

Keep in mind that when it comes to making a change all you need to do is usually change something simple. This will help you start to gain the muscle back. I don't want to sound like an advertisement but if you are looking to really start to make muscle gains I would invest in something like P90X and supplement that with your HIIT workout regime. You will see some good gains from that.

Eat more if you are loosing weight. You can eat more starch and/or more fat. Play with it. If you notice your self going tje wrong way for a few Weeks adjust and re access.

And yikes, HDL that low isn't great. I have read that avocado has been shown to improve HDL/LDL ratio in human test subjects, although I cannot remember where exactly. As far as I know monounsaturated fatty acids are the best for improving cholesterol ratios (olive oil, mixed nuts, avocado, etc). Your diet is good though, lean meats, healthy fats, lots of veggies, some nuts, and fruits and starch depending on where your weight loss is at and your activity levels.

Congratulations again on your success. Love that thing about the doctor. I get stuff like that too, like last time I went for a physical my doctor told me to relax my abs, and I wasn't flexing. Keep up the good work bro. Add in a little carbs and/or fat. Personally, I'd add in some carbs only around workouts, and see how that goes. You could start with 120g sweet potato pre workout and 1 serving of fruit post workout. Or vice versa. You're likely getting a good balance of fats as is- lots of monos and just enough omega 3 and 6. The monos are great because they are more readily burned for energy than saturated, and so are omega 3 and 6. So they are better for staying lean and fit and not regaining any of that weight you lost. These studies show it:

http://www.ergo-log.com/bodyburnsunsaturatedfat.html

http://www.ergo-log.com/monounsaturatedfatboostsepoc.html

http://www.ergo-log.com/fatlossfats.html

http://www.ergo-log.com/oliveoilinsteadofbutter.html

There are more but those are just to prove a point.

Congratulations on getting to this point. My story is somewhat similar to yours, although I have a heavier frame than you. I was 32, 6'1" and 230 lbs and almost magically lost 30+ pounds over on low-carb paleo. I was injured, so I wasn't working out at all.
After that, I decided I wanted to get serious with strength training. I was messed around in the gym multiple times in my life without much results previously. I purchased the book "Starting Strength" by Mark Rippetoe. It is low rep barbell training for beginners. As long as you commit to it (3 1 hour or so workouts per week doing the program as well as eating enough), you should build an impressive amount of strength in 6-9 months, with the weight going up nearly every workout. What program are you currently doing? A few things I have noticed: Low carb paleo is great for losing weight. It is not great for maintaining energy during heavy workouts. Your muscles needs the glycogen manufactured from carbohydrates (or protein turned into glucose in the event of eating low carb) to fuel lifting heavy weights. For workout days, I add in a decent amount of starchy carbs and some fruit. You will need a lot of protein to grow muscles, since you are a beginner and have a lot of room to grow. Try for 1 gram per pound of bodyweight. Adding in additional fat to your diet is useful for helping you bulk up if you still aren't progressing. Basically, as other have said, eat more. Just be generally conscientious of what you are consuming and adjust as necessary. I went down to 195 from 230 and then put on about 12 pounds of muscle in the last 9 months. I am finally getting the hang of dialing in the amount of food to feed my workouts without putting on fat.