Remember, this isn't a quick fix. It sounds like you're doing everything right, it's just going to take a while for your GI tract to "calm" down. Your bloat probably has to do with the fact you're getting in more fiber and eating foods you're not used to. Also, it may be that you were malnutritioned and to begin eating new foods and with more frequency, you're body is just adjusting.
I'll try to explain what happens: When you're not eating certain foods regularly your digestive systems doesn't produce enough of the enzymes needed to digest them. That's why you introduce them in a little at time-- to build up a tolerance by increasing the production of those necessary enzymes. While your body is adjusting, you may experience more gas and bloating because these foods are not getting fully digested and end up in the large intestine where they are broken down by bacteria and create gas. HOWEVER, this effect lessens because, as you continue to eat these foods, your digestive tract starts producing more of those helpful enzymes. This is especially obvious with beans, although they're not something you want to try right away and you want to make sure when (or if) you start eating them that they're pureed, mechanically broken so they're easier for you to digest.
Kate/Wind had a great suggestion with the enzyme supplements. She knows her stuff!