Já que é no Ubuntu, acho que você tem o GNU grep. A página de manual também diz:
grep understands three different versions of regular expression syntax: “basic” (BRE), “extended” (ERE) and “perl” (PCRE). In GNU grep, there is no difference in available functionality between basic and extended syntaxes. In other implementations, basic regular expressions are less powerful. The following description applies to extended regular expressions; differences for basic regular expressions are summarized afterwards.
E então:
Basic vs Extended Regular Expressions
In basic regular expressions the meta-characters?
,+
,{
,|
,(
, and)
lose their special meaning; instead use the backslashed versions\?
,\+
,\{
,\|
,\(
, and\)
.
Portanto, você precisa usar \{3,\}
ou usar o -E
para habilitar os EREs. Eu sugiro o último, já que as barras invertidas em todos os lugares ficam feias rapidamente.