Redmine

1. your database version: MySQL 14.12
2. your Ruby version: Ruby 1.8.7 (i386-mingw32)
3. your Rails version: Rails 2.3.5
4. your Redmine version: 1.1.2 Stable

Create Task 1 with due date today+5
Create Task 2 with due date today+6
Create Task 3 with due date today+7

In Task 3, add relation "Follows" Task 2
In my distribution, the relation isn't shown until I refresh the screen, but that's not the intent of the bug report. If you see the relation added, continue, otherwise hit refresh.

Now, add a second relation "Follows" Task 1. The relation won't be created because Task 1 has an earlier start date than Task 2. If you delete the relation to Task 2 and start over adding Follows Task 1 and then Follows Task 2, it will be accepted.