Can't get much cheaper than a voltage divider; just make sure that your 12V input really is 12. In case it can be a little high, you may want to choose resistors to drop it a little lower than 5V - it'll still register as high.
The 12V is not constant all the time.. It sometimes rises to 16V too..
Use the 12-16V to drive an optoisolator, on the output side pull the open collector low on an arduino input with pullup resistor enabled.
I finally decided to use the 7805 SOT89 package, as I am working on SMD board and the space is a real issue.
I don't think a voltage regulator is the right application, as DVDdoug already told you. It's a shame that you didn't listen. Voltage regulators are designed to POWER something. They are never used to regulate the voltage on a data line. Good luck making that work.