I recently lost a lot of weight (from 107kg to 90kg) using a combination of a lot of bike riding and some nutrition changes, but I don't see any difference in my body size - my gut seems the same size and so are the circumference of arms and legs.
You can't really spot reduce. In other words, you don't have any control of where you'll lose fat. Chances are you have lost some fat all over, even if you haven't noticed visible changes.
In fact, it's not a bad idea to make weekly measurements for this exact reason. You can actually measure your bodyfat pretty easily with a simple set of bodyfat calipers (instructions come with the calipers) along with a bathroom scale. Not only is it encouraging to know you're making progress, but you can even adjust your diet and exercise regimen accordingly if you determine that you're losing muscle, for example.
If you're interested in changing your body composition, building muscle, and losing fat then I'd look into high-intensity interval training (HIIT) as demonstrated here. Some exercises done with HIIT may be more anaerobic than others and you can pick and choose your routine based on your goals. But whatever you do, be smart and track your progress with bodyfat measurements. It literally takes 2 minutes and you only have to do it once a week.
