For what it is worth, you have described the pairing process correctly It should be working for you.
Make sure you have gone back "out" to the the top level of the REMOTE APP interface. You should see a selction of AppleTV's [at least one] on the list.
Select the 1st Apple TV from the list. This will bring you to the "playlists" itune list [probably]
Observe the bottom of the screen and you should see
Playlists - Artists - Control-Search-More
Obviously, you want to select "Control" It has the four arrows pointing North/South/East/West.
Once you select the "Control" tab, you should see the familiar Menu and "TackPad" interface that you are looking for.
I have a 1st Gen and 2 2nd Gen ATV's working, all controlled from Ipad 1 and iPhone [4S].
Everything you described is correct.
Knowledge Base is here for a logical troubleshoot..
I have the same exact issue. how did you resolve it in the end. I have paired succesfully but I cannot see the control section. It is like i'm connected to an itunes library on my computer.
I also have the first generation apple tv and before apple remote 3.0 I had no issues seeing and controlling my apple tv with this app via the touch control menu.
Its like its not seeing the apple tv as an apple tv, rather just seeing it as an itunes library on a computer