I am having the same problem with the Android app on both a new Samsung S4 and a new Samsung Tab2 tablet. The Collect New icon appears and the application works fine on an iPhone. Although, I have noticed the missing icon occasionally when I load a map onto my iPhone, the icon will appear if I exit and then reload the map. I've tried deleting the application cache on the Android devices, in an effort to reload the map, but with no luck.
We have an older collection map that works fine on both the iPhone and Android. The map I'm having a problem with is something I've been working on over the past few days, and have had to rebuild a couple of times, changing the fields, etc.
Any help would be most appreciated!!