My Google Voice services keeps getting stuck on “restarting”
I haven't seen this particular issue before, but Kevin Purdy's "Holy Trinity" of steps to take with apps that just aren't working properly is:

From Settings | Applications | Manage applications | &lt;application&gt;


Force stop


if that doesn't help


Clear cache


if that doesn't help


Clear data


and if that still doesn't help, try the nuclear option: 


uninstall and re-install