Вероятно си объркал нещо при конфигурацията на сървъра. При мен, на моя хостинг, без да променям каквото и да е от примера, който си дал
Код:
RewriteEngine on
RewriteRule ^genre:([0-9]+)/$ index.php?page=genre&id=$1 [L]
Зареждам http://mydomain.com/genre:1/
Резултат:
Код:
Array ( [page] => genre [id] => 1 )
Потърси проблема другаде, не е в кода