Welcome, Scott! Glad to hear you decided to look into the nutrition side of the equation -- I think you'll find that, when it comes to fat loss, nutrition is far and away the most important side.
Does your personal trainer have you lifting heavy things and sprinting, as opposed to doing a lot of steady-state cardio?
Don't worry about the lettuce thing! Spinach has more nutritional bang for your buck anyway. I almost never buy lettuce, but I always have a huge bag of spinach on hand. Also, if you aren't crazy about salads, there are a million other ways to eat your veggies.
Looking forward to your updates.