While bees communicating the location of a food source through movement to others can be seen has intelligence, I don't believe humans as a whole would consider it significant enough.
The minimum requirement could quite possibly be the ability to record history.
It would not need to be as advanced as written text but the simple pictures in a cave showing migration to a food source for future generations.
To be successfully recognised as intelligent you first have to be recognised as life. Being recognised as life requires that metabolic rate and scale are tangible. If an organism meets every other criteria for intelligence but does it on a geological scale then everything that a human can observe in human terms will be ascribed to geological process.
Similarly, no matter how complicated our own activities, that organism would regard us as an unintelligent parasite.
So, to be recognised as intelligent by, and to some extent for that intelligence to be in any way relevant to, humans you have to act with a tempo within the grasp of humans.
Intelligence is inherently linked to work. Work is an organized form of changing our environment. Bees and ants do work and change the environment, but they do so in a pattern organized by their genomes. Intelligent work is characterized by its capability to be taught to others of the same species. A human being is not born knowing how to build houses like ants do. It is taught how to do so by someone who already knows. This kind of accumulated knowledge that is first transmitted by alive members of the species, later evolves, with writing, as a multigeneration accumulation of knowledge and culture.
So, to verify if some species is intelligent you might ask:
Does this species change the environment?
Does this species change the environment via organized work?
Does this species create new kinds of work and tools out of
If this species does create new kinds of work and tools, does it do so by
genetic change or learned behaviour?
Does this species pass their knowledge from one generation to the
next via teaching?
Does this species write down their knowledge so it can be furthered
by the next generations?
Up to the fourth question you are still in the realm of primate intelligence on Earth, because each one of those things can be done by various primate species. The questions five and six are humankind development.
Now what traits does a species need, to be recognized as intelligent by humans,
beyond the fact that it is sentient and recognizable as alive by humans?
Differently put, this question could also be: what type of sentient species will >we miss out because of our inability to recognize their sentience?
The beings must:
1) Have the ability to accomplish complex tasks with results that are detectable (by humans), that are beyond the complexity achieved by non-sentient animals (as defined by the culture that encounters them), or
2) Have the (apparent) ability to communicate non-immediate or complex abstract concepts with one another (or with us), and
3) Operate on something close to the same timescale.
Or, to answer the reverse: Humans are not likely to recognize as sentient any race of beings that neither performs tasks more complex than nest-building or poking anthills with sticks, nor has any apparent means of communication more complex than required to signal dangers, the presence of food, the desire to mate, etc. Nor are we likely to recognize a sentience that requires day to say hello.
Motion will almost certainly be the most obvious thing that will make humans sit up and take notice. The ability to move, and to sense motion, is the subject of too many studies to mention. Conversely, if a species is sessile (and the spell checker sure doesn't like that word!), it will likely be overlooked for years, if it's ever spotted at all. Note that this isn't a requirement for sentience, just a focal point for human investigation.
Communication is probably the next biggest thing. Vocal communication attracts our attention as a species, and we tend to make big assumptions about species that don't operate this way. Electromagnetic phenomena will also almost certainly be noticed immediately. Body language is something that a trained observer would probably notice, especially if the species is highly gregarious, but this is the point at which arguments will develop about whether or not this form of communication constitutes sentient intelligence. Species that use chemical, "psychic" (for a certain value of psychic), and other more exotic forms of communication will almost certainly be overlooked for a long time.
Gregarity will also be a valuble clue. If a species, especially a spacefaring species, has such a sparse population as to rarely encounter other members of the same species, it might be hard to recognize an extraterrestrial species for what it is, never mind identify it as intelligent.
Technology is, of course, a dead giveaway, or it ought to be. Certainly anyone that thinks the great apes are sentient would see even the most primitive tech as a sign of intelligence. The famous termite fishing sticks come to mind.
Nervous Biology (Let the jokes begin!) For a species that isn't noted as sentient by any other method, biological examination might be used to try to determine the level of intelligence of that species. Current day scientists put a lot of stock in the Anthropic Principle, at least in the sense that they expect intelligent life to have a nervous system that functions like our does. Even xenobiologists that expect a physical nervous system radically different from our own aren't sure that they'll know what they're looking at when they see it. By this measure, if we ever accepted that some species with such a radically different biology was indeed sentient, we'd have much better clues to search for. Until then, only species that really resemble us are likely to be spotted in this way.