When they say "new line installed", they normally mean going through the standard motions of connecting your existing line up to the exchange. I moved into my new flat at the start of last year, which is a new build. The physical line is put in to the property, along with everyone elses. But it then has to be connected up to the exchange, assigned a phone number, and all that jazz. This comes under the umbrella of a "new line" install.
The physical line is most likely there, but it just not connected (you can find that out easily enough by plugging a phone into the master socket - there should be no dial tone).
New line installs aren't cheap. Depending on who you go with, it will probably be around the £100 mark (BT might do it cheaper if you go with them for line and broadband). The previous occupier of the flat no doubt ceased the line, which is a perfectly normal thing to do. Any cease and re-provide of a line normally requires a "new line" to be installed.