How do I write functional tests for programs with a Curses user interface?

I'm using Python to write a simple command-line program with the following use case:

1. When launched, a list of records from a database is presented.
2. As the user types the records are filtered.
3. The newly filtered list is presented after each key press.

To present live updates, I am using the Curses library to obtain key-press events and to present the list to the console as it is filtered. Please note that I've simplified this; the program may perform a variety of actions depending upon what keys are pressed and when.

The program is divided into three modules:

1. Database - Essentially a single-table list.
2. UI - An abstraction-layer over the Curses library.
3. App - Collects key-press signals from the UI, queries the database, and tells the UI what output is expected.

The difficulty I'm having is finding a robust strategy for testing this program. Unit tests are not the issue; I'm asking about functional tests. I want to test, for example, that when launched the program presents an unfiltered list; that subsequently, when the 'A' key is pressed the program presents a properly filtered list, etc.

When testing a web app my tests may run the app on a server. They can then use Selenium to simulate a browser session and test that I can navigate from A to B, or perform some task, etc. I don't have a similar way of simulating a console session and connecting to my Curses program.

Instead, I've sub-classed my UI to provide a TestUI which does not use the Curses library. I can now run the App in a separate process/thread and interact with it by sending messages to a TestUI instance. There are two problems with this approach:

1. I'm not really testing my UI's functionality because I'm using a different UI!
2. Testing is impacting the UI's implementation. Because the test-suite shares the UI with an app thread, any UI interactions need to happen using synchronised or thread-aware structures. For example, I cannot store key-presses in a list or a deque - the natural choices - instead I must use a Queue.

Something feels wrong here - surely this can't be a new problem! What strategies are available to me to test my Curses program?