It's personal data
It's unfortunate for her that May has compared the "Internet Connection Record" to an "itemised telephone bill".
The ICO's own quick reference guide about what is "personal data" says "Data such as personal bank statements or itemised telephone bills will be personal data about the individual operating the account or contracting for telephone services. ".
So our internet connection records are personal data under the Data Protection Act. The ISPs will have to treat the data as such.
They must respond to subject access requests.
They must also ensure that appropriate protection is applied to this personal data.
They must delete it when no longer required.
More interestingly, the ISP must declare to the customer the reason for storing this data, and obtain the customer's consent.
Have they thought this through?