The problem is not the amount of memory. It is the card itself. The Sandisk microSDHC card with adapter 16 GB UPC 6 19659 06688 8 will work on the Roku Ultra, but not on the Roku 3, so they may not work on the Roku 2 either.
Purchased a Samsung EVO 16 GB Class 10 microSDHD UHS-I card with adapter UPC 8 87276 96937 4 from Amazon. It works just fine.
I have relied on San Disk for years for my camera, but their cards, regardless of the amount of memory, just didn't work on the older Roku models.