Why do I get phone storage is getting low when I've un-installed almost all apps?
Maybe because you haven't removed only the small apps that doesn't take significant space.

Go to settings -> Apps -> Select "All" on apps tab -> Click menu and click sort by size.

You'll see the apps sorted by the size it takes on your phone. Check if the top apps in this list are taking most of your space.