I have uncles and cousins who married non-Jewish women but had their boys have brit-millah when they were babies. Are they considered Jewish under orthodox Judaism?
No they are not Jewish.
Judaism is inherited from the mother. Having or not having a bris has no effect on if a person is Jewish.
I'm a little surprised the child had a brit - usually the mohel (person doing the circumcision) checks first if the child is actually Jewish to avoid situations like this. Perhaps it was a medical circumcision not a brit?
Also, you ask "under orthodox Judaism", but I believe this is true under most branches. (With the notable exception of Reform - but even they require that the child be a continual part of the Jewish community, which I suppose, is their version of conversion.)
But, I'm glad you asked - these differing definitions are a cause of some huge problems in the Jewish community, especially when someone becomes a Ba'al Teshuvah and then wishes to get married.
To sum up some previous conversation, Jewish status is matrilineal, so the child of a Jewish father and non-Jewish mother is not Jewish.
There are mohels who will do a circumcision on such a baby with a panel of three rabbis observing, stating "this is a first step towards conversion if they choose to go that way." That means at some point in the future, if this child grows up and wants to be considered Jewish according to the Orthodox definition (or if the parents decide they want to move towards more Orthodox affiliation), all they need is a dunk in the mikvah -- bloodless, hooray!
It's even been suggested that as long as the circumcision was done by a Jew with proper technique and with the intent of "following Jewish law" (without explicitly stating "this is for conversion", e.g. the mohel just assumed this was a Jewish baby), that would suffice as a step towards conversion.