Thank you all for the help! You guys are awesome!

Yeah, there was something wrong with the bottom faces indeed.

So from my understanding I will try to have shapes as clean as possible before filleting.
In General as a workflow, do I fillet things as I go or, is it done as a final edge polish pass?

Its a little hard for me to understand in which circumstances the fillet function will work, or not. But I guess in most cases it is because I am doing something wrong. :D