First let me say that I am not a lawyer, and you should not, under any circumstances, rely on me for definitive legal advice. Now that the disclaimer is out of the way, on to my answer.
Bejeweled is a trademark of PopCap Games, so clearly the exact name is off limits. Games with similar names may also be out of bounds as well (see examples below). For example creating a game called Mejeweled or Bejewels would likely be considered a violation of PopCap's trademark of the term Bejeweled. Two high profile examples come to mind with regards to using similar names for similar software products and duplicating functionality.
The first example is Linspire, the Linux distribution formerly known as Lindows. The name Lindows was considered by Microsoft to be an infringement of their Windows trademark, so Microsoft sued them. Microsoft lost in court, appealed, and eventually settled with Linspire. Microsoft paid Linspire $20 million in exchange for changing the name of the product from Lindows to Linspire. From the Linspire Wikipedia article:
In 2002 Microsoft sued Lindows, Inc.
claiming the name Lindows constituted
an infringement of their Windows
trademark. Microsoft's claims were
rejected by the court, which asserted
that Microsoft had used the term
windows to describe graphical user
interfaces before the Windows product
was ever released, and that the
windowing technique had already been
implemented by Xerox and Apple
Computer many years before. Microsoft
sought a retrial and after this was
postponed in February 2004, offered to
settle the case. As part of the
licensing settlement, Microsoft paid
an estimated $20 million, and Lindows,
Inc. transferred the Lindows trademark
to Microsoft and changed its name to
Linspire, Inc.
As the quote suggests, Microsoft lost largely because of a combination of the generic name of the operating system and prior usage of the term "windows" in earlier windowing operating systems. This really isn't the case with Bejeweled and its clones, so that argument may not hold up in court. Either way, the cost of waging a legal battle with Microsoft or even PopCap games would be significant, so it would be best to avoid similar names.
The other example involves Scrabble. This case differs from the Linspire one because it involves the duplication of gameplay and the use of a very similar name. A popular Facebook application named Scrabulous (now called Lexulous) duplicated the functionality of the popular board game Scrabble almost exactly, without the permission of Hasbro, the owner of the Scrabble trademark in the US and Canada. The board layout, point scores, and name were all very similar to what one would find in Scrabble.
"According to Anthony Falzone, head of the Fair Use Project at Stanford University, copyright laws do not allow someone to freely copy the particular expression of an idea" (Scrabulous Wikipedia article). Based on that quote, it would seem copying the gameplay exactly may be out of bounds as well. Hasbro took legal action against the developers of Scrabulous, resulting in a name changed (to Lexulous) and changes to the rules to less closely resemble those of Scrabble. The Wikipedia article lists the consequences:
On July 24, 2008, Hasbro formally sued Rajat Agarwalla and Jayant Agarwalla, along with their company, RJ Softwares. The suit claims Scrabulous violates the Digital Millennium Copyright Act and infringes upon Hasbro's intellectual property rights.
On July 29, 2008, Scrabulous was shut down on Facebook for users in North America, with the error message, "Scrabulous is disabled for US and Canadian users until further notice. If you would like to stay informed about developments in this matter, please click here." Hasbro, the owner of the rights to Scrabble in North America has released a free legal version of Scrabble for Facebook, developed by Hasbro and Electronic Arts.
On 22 August 2008, the application was blocked by Facebook in all countries except India.
On 26 September 2008, the web site at www.scrabulous.com was suspended. This followed a ruling by the Delhi High Court that although the game Scrabble itself could not be copyrighted, and the Agarwalla brothers could therefore continue to offer their similar game online, they would not be permitted to use the name Scrabulous or any other name similar to that of Scrabble.
On 27 September 2008, the game became available once more, with the new name Lexulous.com. There was a makeover, but the essential elements of the old game had been retained, along with all past records, user IDs and saved information intact.
The situation with Bejeweled may be even more complex, because it actually borrows ideas from earlier matching games as well, so any legal action from PopCap would presumably have to include proof that the matching system in Bejeweled was an original idea.
To try to answer your question: Based on my research, PopCap Games could likely sue most of the developers of Bejeweled clones, and perhaps even win settlements, if they can prove (1) the name of the competing product is sufficiently similar, or (2) the functionality exactly duplicates what is in Bejeweled, or (3) graphics or code from Bejeweled were copied and used in the competing product. The last would be a case of copyright infringement rather than trademark infringement.
I know that isn't exactly a concrete answer, but as is often the case with these situations, there is a lot of "gray area" until it is actually brought to court. At the very least I hope this has given you a couple useful examples that you can explore.