I think its common for database tests to include CRUD operations. So these functions modify the database making the expected vales change: eg. if I test that a SELECT returns 2 rows, if a delete test runs 1st, I might just get a failure. Similar to INSERT. JUnit doesn't appear to run tests as they are defined, making expected values hard.
If I have my database reinitialized at every test, it maybe overkill and slow. So how might I approach this problem?
Yes, as Steve Hall pointed out, using transactional tests solves the problem of database consistency between tests and test runs 100%. Spring offers very elaborate support for this type of tests (see transaction management in TestContext Framework) but it is not that difficult to implement without it.
Inside transactional tests that rollback their transaction at the end you are free to apply any CRUD operations to your data as long as they are part of the transaction initiated by the test. Then single rollback during test tear down eliminates all CRUD effects on the database.