Here's a thought. Is this a pay app or a free app? is it written by a single person or an established company (this is vague)? Is it just a functionality app, or do you see the person trying to make money off of it.
What I'd do if it's a free app, is contact that owner and see if he has plans to bring it to the Android? You never know, maybe he doesn't but he'll let you have to code to do it yourself.
I think a big piece of it is intent. Are you trying to get rich off the app or are you trying to stop them from making money? If so, you're probably going to have problems if they want to make a case about it (and that's a big if).
Or are you just finding something that's useful on the iPhone and want to do it on the Android? In that case, it's less likely to be a problem. As others have said, make sure your app is different (doesn't have to be in a big way, just make it different in some minor way)
We have a number of android apps that are actually pay apps that are rip offs of Bejeweled with their own twists and no one is suing anyone. Puzzle quest is just also a rip off of Bejeweled.. As long as you aren't trying to steal everything from the app you should be ok.