The widget doesn't appear in the widget list on Android 4.0 until after the phone is rebooted.
This was verified in the ICS emulator. A possible fix is to add a launcher icon for the app. See this StackOverflow post.
This app already has an android.intent.category.INFO activity that can be launched form the Market though. Does this make any difference when doing an actual Market install?
See Android Issue 24208.